Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

B. Block Adventure
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Гильдон играет в компьютерную игру под названием Block Adventure. В ряд выставлены $$$n$$$ столбиков из кубиков, эти столбики пронумерованы от $$$1$$$ до $$$n$$$. Все кубики имеют равную высоту. Высота $$$i$$$-го столбика равна $$$h_i$$$ — числу кубиков в $$$i$$$-м столбике.

Гильдон играет за персонажа, который может стоять лишь наверху любого столбика. В начале игры персонаж стоит на $$$1$$$-м столбике. Цель игры — оказаться на $$$n$$$-м столбике.

У персонажа есть рюкзак, в который он может положить сколько угодно кубиков. Когда персонаж стоит на $$$i$$$-м столбике, Гильдон может выполнить одно из следующих трех действий сколько угодно раз:

  • если в $$$i$$$-м столбике есть хотя бы один кубик, то можно убрать один кубик с этого столбика и положить его в рюкзак;
  • если в рюкзаке есть хотя бы один кубик, можно один кубик достать и положить на $$$i$$$-й столбик;
  • если $$$i < n$$$ и $$$|h_i - h_{i+1}| \le k$$$, можно передвинуть персонажа на верх $$$i+1$$$-го столбика. $$$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».

Вы можете выводить каждую букву в любом регистре (строчную или заглавную).

Пример
Входные данные
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
Выходные данные
YES
NO
YES
NO
YES
Примечание

В первом случае Гильдон может забрать один кубик из $$$1$$$-го столбца, перейти во $$$2$$$-й столбец, положить кубик на $$$2$$$-й столбец, а затем перейти в $$$3$$$-й столбец.

Во втором случае Гильдон должен положить кубик из рюкзака на $$$1$$$-й столбец, чтобы попасть во $$$2$$$-й. Но тогда уже не получится попасть в $$$3$$$-й столбец, так как $$$|h_2 - h_3| = 3 > k$$$ и невозможно уменьшить эту разницу.

В пятом случае персонаж изначально на $$$n$$$-м столбце, поэтому игра выиграна сразу.