Gildong 正在玩一款名为“方块冒险”的视频游戏。在《方块冒险》中,一行中有 $$$n$$$ 列方块,列编号从 $$$1$$$ 到 $$$n$$$。所有块都具有相同的高度。第 $$$i$$$ 列的高度表示为 $$$h_i$$$,即第 $$$i$$$ 列中堆叠的块数。
Gildong 作为一个只能站在柱子顶部的角色来玩游戏。一开始,角色站在 $$$1$$$-st 列的顶部。游戏的目标是将角色移动到第 $$$n$$$ 列的顶部。
该角色还有一个可以容纳无限多个方块的袋子。当角色位于第 $$$i$$$ 列的顶部时,Gildong 可以根据需要多次执行以下三个操作之一:
- 如果该列上至少有一个方块,则从第$$$i$$$列的顶部移除一个方块并将其放入袋子中;
- 如果袋子里至少有一个方块,则从袋子里取出一个方块并将其放在第 $$$i$$$ 列的顶部;
- 如果 $$$i < n$$$ 且 $$$|h_i - h_{i+1}| \le k$$$,将字符移动到 $$$i+1$$$-st 列的顶部。 $$$k$$$ 是游戏开始时给出的非负整数。请注意,只能移动到下一列。
在前两种类型的动作中,角色保留在第 $$$i$$$ 列中,并且值 $$$h_i$$$ 发生变化。
角色的包里最初有 $$$m$$$ 块。吉尔东想知道是否有可能赢得比赛。帮助吉尔东找到问题的答案。
输入
每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $$$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$$$ 列的初始高度。
输出
对于每个测试用例,如果有可能赢得比赛,则打印“YES”。否则,打印“NO”。
您可以以任何大小写(大写或小写)打印每个字母。
示例
输入 #1
5 3 0 1 4 3 5 3 1 2 1 4 7 4 10 0 10 20 10 20 2 5 5 0 11 1 9 9 99
输出 #1
YES NO YES NO YES
注意
在第一种情况下,Gildong 可以从 $$$1$$$-st 列中取出一个块,移动到 $$$2$$$-nd 列,将块放在 $$$2$$$-nd 列上,然后移动到 $$$3$$$-rd 列。
在第二种情况下,Gildong 必须将块放在 $$$1$$$-st 列的包中才能到达 $$$2$$$-nd 列。但不可能到达 $$$3$$$-rd 列,因为 $$$|h_2 - h_3| = 3 > k$$$ 并且无法缩小差距。
在第五种情况下,角色从一开始就已经位于第 $$$n$$$ 列,因此游戏立即获胜。