A11470 | 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?

The first line contains four integers $n$ , $W$ , $B$ , $X$ ( $1<=n<=10^{3},0<=W,B,X<=10^{9}$ ) — 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}<=10^{4}$ ) — 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}<=10^{9}$ ), where $cost_{i}$ is the mana cost to summon a bird from the $i$ -th nest.

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