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.