CF1200B.Block Adventure

Gildong is playing a video game called Block Adventure. In Block Adventure, there are $n$ columns of blocks in a row, and the columns are numbered from $1$ to $n$. All blocks have equal heights. The height of the $i$-th column is represented as $h_i$, which is the number of blocks stacked in the $i$-th column.

Gildong plays the game as a character that can stand only on the top of the columns. At the beginning, the character is standing on the top of the $1$-st column. The goal of the game is to move the character to the top of the $n$-th column.

The character also has a bag that can hold infinitely many blocks. When the character is on the top of the $i$-th column, Gildong can take one of the following three actions as many times as he wants:

• if there is at least one block on the column, remove one block from the top of the $i$-th column and put it in the bag;
• if there is at least one block in the bag, take one block out of the bag and place it on the top of the $i$-th column;
• if $i \lt n$ and $|h_i - h_{i+1}| \le k$, move the character to the top of the $i+1$-st column. $k$ is a non-negative integer given at the beginning of the game. Note that it is only possible to move to the next column.

In actions of the first two types the character remains in the $i$-th column, and the value $h_i$ changes.

The character initially has $m$ blocks in the bag. Gildong wants to know if it is possible to win the game. Help Gildong find the answer to his question.

吉尔东正在玩一款名为“方块冒险”的视频游戏。在“方块冒险”中，一行排列着 $n$ 列方块，列从 $1$ 编号到 $n$。所有方块高度相等。第 $i$ 列的高度记为 $h_i$，即该列堆叠的方块数量。

吉尔东以一个角色进行游戏，该角色只能站在各列的顶端。初始时，角色位于第 $1$ 列的顶端。游戏目标是将角色移动至第 $n$ 列的顶端。

该角色还携带一个可容纳无限多个方块的背包。当角色位于第 $i$ 列顶端时，吉尔东可任意多次执行以下三种操作之一：

• 若该列至少有一个方块，则从第 $i$ 列顶端移除一个方块，并将其放入背包；
• 若背包中至少有一个方块，则从背包中取出一个方块，并将其放置于第 $i$ 列顶端；
• 若 $i \lt n$ 且 $|h_i - h_{i+1}| \le k$，则将角色移动至第 $i+1$ 列顶端。其中 $k$ 是游戏开始时给定的一个非负整数。注意：角色仅能向下一列移动。

在前两类操作中，角色始终停留在第 $i$ 列，且 $h_i$ 的值会随之改变。

角色初始时背包中有 $m$ 个方块。吉尔东想知道是否能够赢得游戏。请帮助吉尔东判断这个问题的答案。

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \le n \le 100$, $0 \le m \le 10^6$, $0 \le k \le 10^6$) — the number of columns in the game, the number of blocks in the character's bag at the beginning, and the non-negative integer $k$ described in the statement.

The second line of each test case contains $n$ integers. The $i$-th integer is $h_i$ ($0 \le h_i \le 10^6$), the initial height of the $i$-th column.

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 100$，$0 \le m \le 10^6$，$0 \le k \le 10^6$）——分别表示游戏中的列数、角色初始背包中的方块数量，以及题目描述中所述的非负整数 $k$。

每个测试用例的第二行包含 $n$ 个整数。其中第 $i$ 个整数为 $h_i$（$0 \le h_i \le 10^6$），表示第 $i$ 列的初始高度。

For each test case, print "YES" if it is possible to win the game. Otherwise, print "NO".

You can print each letter in any case (upper or lower).

对于每个测试用例，如果可以赢得游戏，则输出 “YES”；否则输出 “NO”。

你可以以任意大小写（大写或小写）输出每个字母。

In the first case, Gildong can take one block from the $1$-st column, move to the $2$-nd column, put the block on the $2$-nd column, then move to the $3$-rd column.

In the second case, Gildong has to put the block in his bag on the $1$-st column to get to the $2$-nd column. But it is impossible to get to the $3$-rd column because $|h_2 - h_3| = 3 \gt k$ and there is no way to decrease the gap.

In the fifth case, the character is already on the $n$-th column from the start so the game is won instantly.

在第一种情况下，吉尔东可以从第 $1$ 列取走一个方块，移动到第 $2$ 列，将该方块放置在第 $2$ 列上，然后移动到第 $3$ 列。

在第二种情况下，吉尔东必须先将手中背包里的方块放在第 $1$ 列，才能到达第 $2$ 列。但此时无法到达第 $3$ 列，因为 $|h_2 - h_3| = 3 \gt k$，且无法缩小这一高度差。

在第五种情况下，角色初始位置即为第 $n$ 列，因此游戏立即获胜。