C. Разослать сообщения
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Степан — очень занятой человек, сегодня ему нужно отправить $$$n$$$ сообщений в моменты времени $$$m_1, m_2, \dots m_n$$$ ($$$m_i < m_{i + 1}$$$). Но, к сожалению, к моменту времени $$$0$$$ на его телефоне осталось всего $$$f$$$ единиц заряда. В момент времени $$$0$$$ телефон включен.

За одну единицу времени включенный телефон теряет $$$a$$$ единиц заряда. Также в любой момент времени Степан может выключить телефон и включить его позже. Это действие израсходует $$$b$$$ единиц энергии за раз. Считайте включение и выключение моментальным, то есть вы можете включить его в момент $$$x$$$ и послать сообщение в тот же момент и наоборот, послать сообщение в момент $$$x$$$ и выключить телефон в тот же момент.

Если в какой-то момент уровень заряда опускается до $$$0$$$ (становится $$$\le 0$$$), то отправить сообщение в этот момент времени невозможно.

Так как все сообщения очень важны для Степана, он хочет узнать, сможет ли он отправить все сообщения, без возможности зарядить телефон.

Входные данные

В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте. Далее следуют описания наборов.

Первая строка каждого набора содержит четыре целых числа $$$n$$$, $$$f$$$, $$$a$$$ и $$$b$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le f, a, b \le 10^9$$$) — количество сообщений, изначальный заряд телефона, расход заряда за единицу времени и расход при последовательном выключении и включении.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$m_1, m_2, \dots, m_n$$$ ($$$1 \le m_i \le 10^9$$$, $$$m_i < m_{i + 1}$$$) — моменты времени, в которые нужно отправить сообщения.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если Степан сможет отправить все сообщения и «NO» в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
6
1 3 1 5
3
7 21 1 3
4 6 10 13 17 20 26
5 10 1 2
1 2 3 4 5
1 1000000000 1000000000 1000000000
1000000000
3 11 9 6
6 8 10
12 621526648 2585904 3566299
51789 61859 71998 73401 247675 298086 606959 663464 735972 806043 806459 919683
Выходные данные
NO
YES
YES
NO
NO
YES
Примечание

В первом наборе входных данных примера в момент времени $$$0$$$ заряд телефона равен $$$3$$$. При отправке сообщения в момент времени $$$3$$$ без выключения будет потрачено $$$(3 - 0) \cdot 1 = 3$$$ единицы заряда, в таком случае заряд упадёт до $$$0$$$ и Степан не сможет отправить это сообщение. При выключении и включении заряд телефона уменьшится на $$$5$$$, а значит и таким образом отправить сообщение не получится.

Во третьем наборе входных данных примера в момент времени $$$0$$$ заряд телефона равен $$$10$$$, за одну единицу времени телефон теряет $$$1$$$ единицу заряда, а при выключении и включении — $$$2$$$ единицы заряда. Чтобы отправить все сообщения можно действовать следующим образом:

  • Выключить телефон в момент времени $$$0$$$ и включить в момент времени $$$1$$$, после этого останется $$$10 - 2 = 8$$$ единиц заряда;
  • отправить сообщение в момент времени $$$1$$$;
  • отправить сообщение в момент времени $$$2$$$, после этого останется $$$8 - (2 - 1) \cdot 1 = 7$$$ единиц заряда;
  • Выключить телефон в момент времени $$$2$$$ и включить в момент времени $$$3$$$, после этого останется $$$7 - 2 = 5$$$ единиц заряда;
  • отправить сообщение в момент времени $$$3$$$;
  • Выключить телефон в момент времени $$$3$$$ и включить в момент времени $$$4$$$, после этого останется $$$5 - 2 = 3$$$ единиц заряда;
  • отправить сообщение в момент времени $$$4$$$;
  • Выключить телефон в момент времени $$$4$$$ и включить в момент времени $$$5$$$, после этого останется $$$3 - 2 = 1$$$ единиц заряда;
  • отправить сообщение в момент времени $$$5$$$.

Последний (шестой) набор примера может упасть, если в вашем решении есть переполнение целочисленного типа.