Birds
Contest: Codeforces Round 461 (Div. 2)
Difficulty rating: 2200
Tags: dp

Apart from plush toys, Imp is a huge fan of little yellow birds!

To summon birds, Imp needs strong magic. There are n trees in a row on an alley in a park, there is a nest on each of the trees. In the i-th nest there are ci birds; to summon one bird from this nest Imp needs to stay under this tree and it costs him costi points of mana. However, for each bird summoned, Imp increases his mana capacity by B points. Imp summons birds one by one, he can summon any number from 0 to ci birds from the i-th nest.

Initially Imp stands under the first tree and has W points of mana, and his mana capacity equals W as well. He can only go forward, and each time he moves from a tree to the next one, he restores X points of mana (but it can't exceed his current mana capacity). Moving only forward, what is the maximum number of birds Imp can summon?

Input format:
The first line contains four integers n, W, B, X (1 ≤ n ≤ 103, 0 ≤ W, B, X ≤ 109) — the number of trees, the initial points of mana, the number of points the mana capacity increases after a bird is summoned, and the number of points restored when Imp moves from a tree to the next one.

The second line contains n integers c1, c2, ..., cn (0 ≤ ci ≤ 104) — where ci is the number of birds living in the i-th nest. It is guaranteed that $$\sum_{i=1}^{n} c_i \leq 10^4$$.

The third line contains n integers cost1, cost2, ..., costn (0 ≤ costi ≤ 109), where costi is the mana cost to summon a bird from the i-th nest.

Output format:
Print a single integer — the maximum number of birds Imp can summon.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample base amount of Imp's mana is equal to 12 (with maximum capacity also equal to 12). After he summons two birds from the first nest, he loses 8 mana points, although his maximum capacity will not increase (since B = 0). After this step his mana will be 4 of 12; during the move you will replenish 4 mana points, and hence own 8 mana out of 12 possible. Now it's optimal to take 4 birds from the second nest and spend 8 mana. The final answer will be — 6.

In the second sample the base amount of mana is equal to 1000. The right choice will be to simply pick all birds from the last nest. Note that Imp's mana doesn't restore while moving because it's initially full.

Example input:
2 12 0 4
3 4
4 2

Example output:
6

Example input:
4 1000 10 35
1 2 4 5
1000 500 250 200

Example output:
5

Editorial:
The problem can be solved by utilizing dynamic programming.
Let us denote by $$\mathrm{dp}[n][k]$$ the maximum possible remaining amount mana for the state (n, k), where n stands for the number of nests passed by and k stands for the number of birds summoned.
The base is $$\mathrm{d}p[0][0] = W$$ as we have passed by no nests, have summoned no birds and have W mana at our disposal in the beginning. Let us also initialize all other states with ∞.
The transitions are as follows: consider us having walked to the next nest and summoned k additional birds from there, therefore proceeding from the state (i - 1, j - k) to (i, j) (of course, it is reasonable to require that the answer for (i - 1, j - k) is not ∞). After we have proceeded, X units of mana would be replenished (taking summoned birds into consideration, the amount of mana at the moment is bounded above by W + (j - k)·B). The summoning would cost us $$\text{cost}_i \cdot k$$ mana. If after the replenishing and the summoning the remaining amount of mana is nonnegative, we update the answer for the state (i, j):
The answer is the maximal k among reachable states (those not equal to ∞).
Time complexity: $$O\left(n \sum_{i=1}^{n} c_i + \left( \sum_{i=1}^{n} c_i \right)^2 \right)$$. Note that the constant in the square is no more than $$\frac{1}{4}$$.