Espresso Made Your Way

You have a new job. Coffee is not your cup of tea. Many customers ask for a particular ratio of coffee to milk. You cannot make arbitrary measurements. You have two cups of the same size, a machine that dispenses pure coffee, and another machine that dispenses pure milk.

You can completely fill one empty cup with coffee and the second empty cup with milk. You can also take these two full cups and mix them so that the result has exactly half of each cup, that is, half coffee and half milk. This gives you a cup that is half coffee and half milk, but you have wasted a full cup of ingredients (the second half of the coffee and the second half of the milk).

Now that you have a cup that is half coffee and half milk, you can fill the second cup with coffee or fill it with milk. Then you can mix the two cups to create a cup with a different ratio. When mixing two cups, you use exactly half of each cup and waste exactly half of each cup.

By repeating this process, you can make some coffee-to-milk ratios, but some ratios are impossible.

Given the range of coffee-to-milk ratios a customer accepts, determine the least amount of ingredients you will waste when you prepare the order optimally.

There is one input line containing four integers $C_1$, $M_1$, $C_2$, and $M_2$ ($0 \le C_1, M_1, C_2, M_2 \le 10^6$). The customer accepts any ratio from $C_1$ parts coffee per $M_1$ parts milk to $C_2$ parts coffee per $M_2$ parts milk. The two ratios are not identical, $C_1 + M_1 > 0$, $C_2 + M_2 > 0$, and $\frac{C_1}{C_1+M_1} \ne \frac{C_2}{C_2+M_2}$.

Print one integer: the least number of cups of ingredients wasted when the order is prepared optimally.