CF922E.Birds

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 c__i birds; to summon one bird from this nest Imp needs to stay under this tree and it costs him cost__i 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 c__i 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?

除了毛绒玩具，Imp 还特别喜欢小黄鸟！

要召唤鸟类，Imp 需要强大的魔法。公园一条小径上并排生长着 $n$ 棵树，每棵树上都有一个鸟巢。第 $i$ 个鸟巢中有 $c_i$ 只鸟；Imp 若想从该鸟巢中召唤一只鸟，必须站在该树下，且消耗 $cost_i$ 点法力值。然而，每成功召唤一只鸟，Imp 的法力上限就会增加 $B$ 点。Imp 一只一只地召唤鸟类；他可以从第 $i$ 个鸟巢中召唤任意数量（$0$ 至 $c_i$ 只）的鸟。

初始时，Imp 站在第一棵树下，拥有 $W$ 点法力值，且其法力上限也为 $W$。他只能向前移动；每次从一棵树移动到下一棵树时，会恢复 $X$ 点法力值（但不能超过当前法力上限）。在仅允许向前移动的前提下，Imp 最多能召唤多少只鸟？

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 _c_1, _c_2, ..., c__n (0 ≤ c__i ≤ 104) — where c__i is the number of birds living in the i-th nest. It is guaranteed that .

The third line contains n integers _cost_1, _cost_2, ..., cost__n (0 ≤ cost__i ≤ 109), where cost__i is the mana cost to summon a bird from the i-th nest.

第一行包含四个整数 $n$、$W$、$B$、$X$（$1 \leq n \leq 10^3$，$0 \leq W, B, X \leq 10^9$）——分别表示树的数量、初始法力值、每次召唤一只鸟后法力上限的增量、以及小鬼从一棵树移动到下一棵树时恢复的法力值。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$0 \leq c_i \leq 10^4$）——其中 $c_i$ 表示第 $i$ 个鸟巢中栖息的鸟的数量。保证满足 。

第三行包含 $n$ 个整数 $\text{cost}_1, \text{cost}_2, \dots, \text{cost}_n$（$0 \leq \text{cost}_i \leq 10^9$），其中 $\text{cost}_i$ 表示从第 $i$ 个鸟巢中召唤一只鸟所需的法力消耗。

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

输出一个整数——Imp 能召唤的鸟的最大数量。

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.

在第一个样例中，Imp 的初始法力值为 12（最大容量也为 12）。他从第一个鸟巢召唤两只鸟后，损失了 8 点法力值，但其最大容量不会增加（因为 $B = 0$）。此操作后，他的法力值变为 4/12；在移动过程中将恢复 4 点法力值，因此拥有 8/12 的法力值。此时最优策略是从第二个鸟巢召唤 4 只鸟，消耗 8 点法力值。最终答案为 6。

在第二个样例中，初始法力值为 1000。最优策略是直接从最后一个鸟巢召唤全部鸟类。注意：由于初始法力值已满，Imp 在移动过程中不会恢复法力值。