Степан — очень занятой человек, сегодня ему нужно отправить \(n\) сообщений в моменты времени \(m_1, m_2, \dots m_n\) (\(m_i < m_{i + 1}\)). Но, к сожалению, к моменту времени \(0\) на его телефоне осталось всего \(f\) единиц заряда. В момент времени \(0\) телефон включен.
За одну единицу времени включенный телефон теряет \(a\) единиц заряда. Также в любой момент времени Степан может выключить телефон и включить его позже. Это действие израсходует \(b\) единиц энергии за раз. Считайте включение и выключение моментальным, то есть вы можете включить его в момент \(x\) и послать сообщение в тот же момент и наоборот, послать сообщение в момент \(x\) и выключить телефон в тот же момент.
Если в какой-то момент уровень заряда опускается до \(0\) (становится \(\le 0\)), то отправить сообщение в этот момент времени невозможно.
Так как все сообщения очень важны для Степана, он хочет узнать, сможет ли он отправить все сообщения, без возможности зарядить телефон.
Выходные данные
Для каждого набора входных данных выведите «YES», если Степан сможет отправить все сообщения и «NO» в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «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\).
Последний (шестой) набор примера может упасть, если в вашем решении есть переполнение целочисленного типа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|