8516: Climb Stairs

DLee came to a new level. What is waiting for him is a tall building with n floors, with a monster on each stair, the i-th of which has health point ai.

DLee starts from the ground(which can be regarded as the 0-th floor), with a base attacking point a0. He can choose to jump $1,2,\dots ,k$ floors up or walk 1 floor down, but he cannot go to floors whose monster has a health point strictly greater than his attacking point, nor can he go to floors which had been visited. Once he comes and defeats a monster he can absorb his health point and add it to his attacking point.

Note that DLee should always be on floors $0,1,2,3,\dots ,n$.

Now DLee asks you whether it is possible to defeat all the monsters and pass the level.

There are T test cases.

In each test case, the first line contains three integers:n,a0,k(1≤n,k≤105,1≤a0≤109), representing the number of floors, base attacking point, and the maximum number of floors that DLee can jump.

The second line contains n integers a1,…,an(1≤ai≤109), representing the health point of each monster.

The sum of n does not exceed 106.