题目描述

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

输入格式

多组测试数据

第一个整数$\red{T，}$表示测试数据组数。

每组数据第一行三个整数 $\red{b，}$$\red{L，}$$\red{k}$

第二行一个整数 $\red{n}$

第三行$\red{n}$个整数，表示$\red{n}$个区域的攻击值

相邻两组数据有空行

输出格式

共$\red{T}$行

每行一个整数。如果响希能到达城堡就输出他所剩下的最大血量，否则输出$\red{-1}$。

样例

输入样例

2
3 1 2
5
3 3 3 2 2

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

输出样例

-1
4

提示

对于$\red{20\%}$的数据，$\red{1<=n<=10,T<=5,1<=L<=3}$。

对于$\red{100\%}$的数据，$\red{1<=n<=3000,T<=10,1<=L<=300,1<=b，}$$\red{a_i<=5000，}$ $\red{1<=k<=200}$。