J. Valuable Prizes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

At the opening of the olympiad, each participant was given a pen and a notepad. Since, due to budget "optimization", it was not possible to buy any other prizes, so the jury decided to award each awardee with another $$$a$$$ pens and $$$b$$$ notepads, and each winner — with $$$2a$$$ pens and $$$2b$$$ notepads.

Determine the minimum possible number of people who could have participated in the olympiad, if in total $$$c$$$ pens and $$$d$$$ notepads were distributed.

Explanation: the sets of awardees and winners do not intersect.

Input

The input data contain four integers $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$ ($$$1 \le a, b, c, d \le 10^{18}$$$), each integer on a separate line.

Output

Print one integer — the minimum possible number of participants. If there is no solution, print 0.

Examples
Input
2
3
10
12
Output
6
Input
2
3
1
2
Output
0
Note

In the first example, among 6 participants there were either zero winners and two awardees, or one winner and zero awardees.