#P0824. 跳台阶

跳台阶

题目描述

有一条无限延伸的楼梯,你初始位于第 00 级台阶。

你每一步可以选择向上跳跃a1,a2,...,ana_1, a_2, ..., a_n个台阶,不能向下移动。

楼梯上有mm个台阶上有金币,你踏上该台阶即可收集金币,每个台阶的金币只能收集一次。

楼梯上有k1k1个台阶是陷阱,你不能踏上陷阱。

楼梯上有k2k2台阶是打卡点,你必须至少经过一个打卡点。

现在,你想在不踏上陷阱、至少经过一个打卡点的前提下到达第xx级台阶,并尽可能收集更多的金币。

请你算出你能收集到的最大金币数,如果无法在至少经过一个打卡点的前提下到达第 xx 级台阶,则输出 −1-1。

输入格式

第一行输入两个整数n,m,x(1≤n≤10,1≤m≤x≤105)n, m, x(1 \le n \le 10, 1 \le m \le x \le 10^5),分别表示可选跳跃台阶数的个数、有金币的台阶的数量、你想要到达的终点。

接下来输入一行nn个整数a1,a2,...,an(1≤ai≤105)a_1, a_2, ..., a_n (1 \le a_i \le 10^5),表示你可选的跳跃台阶数。

接下来mm行,每行输入两个整数pi,wi(1≤pi≤m,1≤wi≤109)p_i, w_i(1 \le p_i \le m, 1 \le w_i \le 10^9),表示在第pip_i级台阶上有wiw_i个金币。

接下来输入一行两个整数k1,k2(1≤k1,k2<x)k1, k2(1 \le k1, k2 < x),陷阱的数量和打卡点的数量。

接下来输入一行k1k1个整数b1,b2,...,bk1(1≤bi<x)b_1, b_2, ..., b_{k1}(1 \le b_i < x),表示第kik_i级台阶是一处陷阱。

接下来输入一行k2k2个整数c1,c2,...,ck2(1≤ci≤x)c_1, c_2, ..., c_{k2}(1 \le c_i \le x),表示第cic_i级台阶是一个打卡点。

题目保证:上述aia_i各不相同,pip_i各不相同, bib_i各不相同, cic_i各不相同。

输出格式

对于每组测试数据,输出一行一个整数:你在至少经过一个打卡点的前提下到达第 xx 级台阶时所能收集到的最大金币数;如果无法在至少经过一个打卡点的前提下到达第 xx 级台阶,输出 −1-1。

样例

3 3 15
3 4 5
3 10
7 5
12 2
4 2
4 5 6 8
2 7 10
17
3 3 15
3 4 5
3 10
7 5
12 2
5 2
4 5 6 8 9
2 13 14
-1

提示

对于样例11,你可以选择先跳33级台阶到第33级台阶,收集到1010枚金币;再跳44级台阶到第77级台阶,收集到55枚金币,同时打卡;接着跳55级台阶到第1212级台阶,收集到第22枚金币;最后跳33级台阶到第1515级台阶,到达终点,共收集到1717枚金币。

对于样例22,无论每步怎样选择跳跃步数,都无法在经过一个打卡点的前提下到达第 1515 级台阶。