An opponent's P.E.K.K.A. with $$$a_2$$$ attack points and $$$h_2$$$ health points is coming straight for your tower! You quickly deploy your own P.E.K.K.A., with $$$a_1$$$ attack points and $$$h_1$$$ health points. The P.E.K.K.A.'s will battle each other, swinging at each other at the exact time every second until one or both dies. Every swing, your P.E.K.K.A. will remove $$$a_1$$$ health points from your opponent's, and your opponent's P.E.K.K.A. will remove $$$a_2$$$ health points from yours. A P.E.K.K.A. dies when it reaches 0 or less health points. You are unsure if your P.E.K.K.A. can win this battle. Fortunately, you have the Royal Chef on your side! He can feed Pancakes to your P.E.K.K.A. before the battle, making it stronger. For every Pancake, you can choose to increase your P.E.K.K.A.'s attack by 1, or health by 1. Calculate the minimum number of Pancakes the Royal Chef must cook for your P.E.K.K.A. to survive this battle!
The input contains four integers $$$a_1$$$, $$$h_1$$$, $$$a_2$$$, $$$h_2$$$ ($$$1 \le a_1, h_1, a_2, h_2 \le 10^{9}$$$).
Output the minimum number of Pancakes the Royal Chef must cook for your P.E.K.K.A.. If your P.E.K.K.A. is already strong enough to survive the battle, output 0.
4 10 8 12
8
7 7 12 20
19
4 6 2 17
3
1 1 1 100
19
In the first test case, it is optimal to make 8 pancakes. Use all 8 pancakes to increase attack. After the first round of attacks, your P.E.K.K.A. wins with 2 health points remaining.
In the second case, it is optimal to make 19 pancakes. Use 13 on attack, and 6 on health. After the first round of attacks, your P.E.K.K.A. wins with 1 health point remaining.
In the third case, it is optimal to make 3 pancakes. Use 2 on attack, and 1 on health. After the third round of attacks, your P.E.K.K.A. wins with 1 health point remaining.
