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 $a_i$.

DLee starts from the ground(which can be regarded as the 0-th floor), with a base attacking point $a_0$. 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,a_0,k(1\leq n,k\leq 10^5,1\leq a_0\leq 10^9)$, representing the number of floors, base attacking point, and the maximum number of floors that DLee can jump.

The second line contains $n$ integers $a_1,\dots,a_n(1\leq a_i\leq 10^9)$, representing the health point of each monster.

The sum of $n$ does not exceed $10^6$.

For each test case, output "YES" or "NO" to show whether it's possible to defeat all monsters.

4
6 1 4
2 2 1 1 9 3
4 2 2
2 3 8 1
3 1 2
3 1 2
7 2 3
4 3 2 7 20 20 20

YES
YES
NO
NO

2022“杭电杯”中国大学生算法设计超级联赛（4）