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