#P0824. 跳台阶
跳台阶
题目描述
有一条无限延伸的楼梯,你初始位于第 级台阶。
你每一步可以选择向上跳跃个台阶,不能向下移动。
楼梯上有个台阶上有金币,你踏上该台阶即可收集金币,每个台阶的金币只能收集一次。
楼梯上有个台阶是陷阱,你不能踏上陷阱。
楼梯上有台阶是打卡点,你必须至少经过一个打卡点。
现在,你想在不踏上陷阱、至少经过一个打卡点的前提下到达第级台阶,并尽可能收集更多的金币。
请你算出你能收集到的最大金币数,如果无法在至少经过一个打卡点的前提下到达第 级台阶,则输出 。
输入格式
第一行输入两个整数,分别表示可选跳跃台阶数的个数、有金币的台阶的数量、你想要到达的终点。
接下来输入一行个整数,表示你可选的跳跃台阶数。
接下来行,每行输入两个整数,表示在第级台阶上有个金币。
接下来输入一行两个整数,陷阱的数量和打卡点的数量。
接下来输入一行个整数,表示第级台阶是一处陷阱。
接下来输入一行个整数,表示第级台阶是一个打卡点。
题目保证:上述各不相同,各不相同, 各不相同, 各不相同。
输出格式
对于每组测试数据,输出一行一个整数:你在至少经过一个打卡点的前提下到达第 级台阶时所能收集到的最大金币数;如果无法在至少经过一个打卡点的前提下到达第 级台阶,输出 。
样例
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
提示
对于样例,你可以选择先跳级台阶到第级台阶,收集到枚金币;再跳级台阶到第级台阶,收集到枚金币,同时打卡;接着跳级台阶到第级台阶,收集到第枚金币;最后跳级台阶到第级台阶,到达终点,共收集到枚金币。
对于样例,无论每步怎样选择跳跃步数,都无法在经过一个打卡点的前提下到达第 级台阶。