Pássaros
Laurêncio adora pássaros amarelos. Para chamar pássaros, Laurêncio precisa usar sua poderosa magia. Existem árvores na rua de um parque, e a
-ésima delas possui
pássaros. Para chamar um pássaros desta árvore, Laurêncio precisa ficar embaixo da árvore e isso lhe custa
pontos de magia. No entanto, para cada pássaro que Laurêncio chama, sua capacidade mágica é aumentada em
pontos. Laurêncio chama pássaros um por um, e quando está na
-ésima árvore, pode chamar desde
a
pássaros.
Inicialmente Laurêncio se encontra na árvore e possui
pontos de magia, e sua capacidade mágica é igual a
, também. Ele pode apenas seguir em frente, e a cada vez que vai da
-ésima árvore para a
-ésima árvore, ele ganha
pontos de magia (mas nunca pode exceder sua capacidade mágica atual). Se Laurêncio andar desde a primeira árvore até a
-ésima árvore, qual é o maior número de pássaros que pode chamar?
Nota: Se a capacidade mágica de Laurêncio é e a sua quantidida de pontos de magia é
ao andar da
-ésima árvore para a árvore seguinte, seus pontos de magia se tornarão
.
Entrada:
A primeira linha de entrada possui 4 inteiros, ,
,
e
(
,
) - 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 inteiros,
. É garantido que
.
A terceira linha contém inteiros,
.
Saída
Imprima um único inteiro: a quantidade máxima de pássaros que Laurêncio pode chamar.
Exemplos:
ENTRADA |
SAÍDA |
2 12 0 4 3 4 4 2 |
6 |
ENTRADA |
SAÍDA |
4 1000 10 35 1 2 4 5 1000 500 250 200 |
5 |
ENTRADA |
SAÍDA |
2 10 7 11 2 10 6 1 |
11 |