Pássaros

Laurêncio adora pássaros amarelos. Para chamar pássaros, Laurêncio precisa usar sua poderosa magia. Existem $n$ árvores na rua de um parque, e a $i$-ésima delas possui $c_i$ pássaros. Para chamar um pássaros desta árvore, Laurêncio precisa ficar embaixo da árvore e isso lhe custa $custo_i$ pontos de magia. No entanto, para cada pássaro que Laurêncio chama, sua capacidade mágica é aumentada em $B$ pontos. Laurêncio chama pássaros um por um, e quando está na $i$-ésima árvore, pode chamar desde $0$ a $c_i$ pássaros.

Inicialmente Laurêncio se encontra na árvore $1$ e possui $W$ pontos de magia, e sua capacidade mágica é igual a $W$, também. Ele pode apenas seguir em frente, e a cada vez que vai da $i$-ésima árvore para a $(i+1)$-ésima árvore, ele ganha $X$ pontos de magia (mas nunca pode exceder sua capacidade mágica atual). Se Laurêncio andar desde a primeira árvore até a $n$-ésima árvore, qual é o maior número de pássaros que pode chamar?

Nota: Se a capacidade mágica de Laurêncio é $Cap$ e a sua quantidida de pontos de magia é $Q$ ao andar da $i$-ésima árvore para a árvore seguinte, seus pontos de magia se tornarão $min(Cap, Q+X)$.

Entrada:

A primeira linha de entrada possui 4 inteiros, $n$, $W$, $B$ e $X$ ($1 \leq n \leq 10^3$, $0 \leq W, B, X \leq 10^9$) - o número de árvores, a capacidade mágica inicial, a quantidade em que a capacidade mágica aumenta ao chamar um pássaro e o número de pontos mágicos adquiridos ao andar entre árvores.

A segunda linha possui $n$ inteiros, $c_1, c_2, ..., c_n$. É garantido que $\sum_{i=1}^n c_i \leq 10^4$.

A terceira linha contém $n$ inteiros, $custo_1, custo_2, ..., custo_n$.

Saída

Imprima um único inteiro: a quantidade máxima de pássaros que Laurêncio pode chamar.

Exemplos:

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

Para submeter sua solução, use esse link.