Помимо плюшевых игрушек, Имп также обожает маленьких желтых птичек!
Для призыва птичек требуется очень сильное колдунство. На аллее в парке в ряд расположены n деревьев, на каждом из которых находится по одному птичьему гнезду. В i-м гнезде живет ci птичек; чтобы призвать одну птичку из этого гнезда, нужно стоять под этим деревом и потратить costi единиц маны. Однако, за каждую призванную птичку Имп поднимает свой максимальный уровень маны на B единиц. Имп призывает птиц по одной, из i-го гнезда он может призвать от 0 до ci птиц.
Изначально Имп находится у первого дерева и имеет запас маны, равный W, его максимальный уровень маны тоже равен W. Имп может двигаться только вперед, при перемещении между соседними деревьями уровень маны Импа восстанавливается на X (но не может превысить максимальное значение). Двигаясь исключительно вперед, каково максимальное количество птичек, которое может призвать Имп?
Выходные данные
Выведите одно число — максимальное количество птичек, которое можно призвать.
Примечание
В первом примере стартовый запас маны Импа равен 12 (совпадает с максимальным значением 12). После того, как он призовет двух птичек из первого гнезда, он потеряет 8 единиц маны, но максимальный запас не увеличится (т.к B = 0). После этого ваша мана будет равняться 4 из 12; во время перемещения вы восстановите 4 единицы маны, в итоге ко второму дереву Имп подойдет, имея 8 единиц маны из 12 максимально возможных. Теперь разумно взять 4 птички из второго гнезда, потратив на это 8 маны. Итоговый ответ — 6.
Во втором примере стартовый запас маны Импа равняется 1000. Оптимальным выбором будет взять всех птичек из четвертого гнезда. Обратите внимание, что на пути от первого гнезда до четвертого мана восстанавливаться не будет, потому что она изначально полна.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 12 0 4
3 4
4 2
|
6
|
|
2
|
4 1000 10 35
1 2 4 5
1000 500 250 200
|
5
|
|
3
|
2 10 7 11
2 10
6 1
|
11
|