UOJ Logo FLYIOI UOJ

FLYIOI

#23. 恶魔幸存者2

【问题描述】

 在久世响希和峰津院大和的共同努力下,终于消灭了7只Septentrion,拯救了世界。但在此之后峰津院就开始企图支配世界。响希为了不让峰津院的阴谋得逞,独自去他的城堡挑战他。但是峰津院知道响希的强大,于是在路上设置了连续的n个防御区域(编号从1~n),每个防御区有一个攻击值ai。由于朱雀受重伤不能用,响希现在只有一只恶魔——神兽白虎。白虎有一个攻击值k,和最大跳跃值L(假设响希当前在x区域,那么他可以骑着白虎跳到x+1到x+L中的任意一个区域)当响希跳到一个区域x,它只有破坏了这个区域才能继续前进,如果此区域的攻击值ax>k,那么响希就要减少ax-k滴血才能破坏着个防御区,否则响希可以直接破坏它。现在响希的初始血量为b,从第0个位置开始进军,峰津院的城堡在n+1号区域。问响希能否到达城堡,如果能,输出他所能剩下的最大血量,否则输出-1.

【输入格式】

多组测试数据
第一个整数T,表示测试数据组数。
每组数据第一行三个整数 b,L,k
第二行一个整数 n
第三行n个整数,表示n个区域的攻击值
相邻两组数据有空行

【输出格式】

共T行
每行一个整数。如果响希能到达城堡就输出他所剩下的最大血量,否则输出-1

【样例数据】

Input
2
3 1 2
5
3 3 3 2 2

5 3 4
10
6 8 1 5 10 2 3 5 6 9
Output
-1
4

【数据范围】

对于20%的数据,1<=n<=10,T<=5,1<=L<=3.
对于100%的数据,1<=n<=3000,T<=10,1<=L<=300,1<=b,ai<=5000,  1<=k<=200