405186: GYM101821 A Smart Vending

It is a hot Sunday afternoon on a streets of Saint-Petersburg. However, Yandex intern Arcadiy is in the office doing some final edits in his student graduation work. After several hours of a hard work he decided to chill and went to a vending machine downstairs to buy some bottles of his favorite soft drink Kvas-Klass.

This vending machine is very special. It only accepts coins of one ruble and banknotes of one million rubles, and it only sells Kvas-Klass that costs r rubles per bottle. Arcadiy has b banknotes of one million rubles and c coins of one ruble. Initially, vending machine is loaded with d coins that it can use to provide change. The process of buying a single bottle of this fantastic drink goes as follows.

1. Arcadiy inserts some number of banknotes x and some number of coins y. Thus, the total amount of money loaded is z = 10⁶·x + y.
2. Then he presses purchase button. If z is less than r he is asked to put more money inside the machine.
3. If z is greater than or equal to r machine tries to give a change to Arcadiy. Change can only be given with coins, so the number of one ruble coins inside the machine (coins loaded in the machine during this purchase are not considered) should be at least z - r. If the number of coins is insufficient the purchase won't happen.
4. If z ≥ r and the number of coins is sufficient to give change (or change is not required, i.e. z = r) the purchase happens. Vending machine takes x banknotes and y coins (that now can used to provide change for next purchases), returns z - r coins back to Arcadiy and gives him a bottles of desired drink.

Arcadiy only wants to purchase a single bottle, but he is a programmer after all. Now he wonders, what is the maximum possible number of bottles he can buy if he picks an optimal purchase strategy? You may assume the vending machine has infinite number of bottles of Kvas-Klass (that is unfortunately never a case in a real life).

The first line of the input contains two integers b and c (0 ≤ b, c ≤ 10⁹) — the number of one million ruble banknotes and the number of one ruble coins Arcadiy initially possesses.

The second line of the input contains two integers r and d (1 ≤ r ≤ 10⁹, 0 ≤ d ≤ 10⁹) — the price of one bottle of Kvas-Klass and the number of coins in the vending machine at the beginning. Note that the number of banknotes inside the machine doesn't matter.

Print one integer — the maximum number of bottles of Kvas-Klass Arcadiy can buy if he selects an optimal strategy.

21 1000000
1100000 0

20

10 700000
350000 200000

4

In the first sample, Arcadiy can spend all the money he has.

In the second sample, he can first buy two bottles using only the coins he has. Then he buys a bottle with a banknote (there are 900 000 coins inside the machine at this moment so it can give a change). Finally he buys one more bottle.