Two Water Jugs

There are two empty jugs A and B with different capacities. You want to reach a target state, meaning each jug holds a required amount of water, by repeatedly filling and emptying the jugs. Nothing other than the jugs measures water exactly, and only these three operations are allowed.

• F(x): fill jug x to the top. Whether jug x was empty before does not matter, and the other jug is left alone.
• E(x): pour out all the water in jug x. The other jug is left alone.
• M(x,y): pour the water of jug x into jug y. If the amount left in jug x is at most the free space in jug y, all of it goes into y. If it is more than the free space, pour until y is full and keep the rest in x.

The notation $(p,q)$ means jug A holds $p$ liters and jug B holds $q$ liters.

For example, let the capacities of jugs A and B be 2 liters and 5 liters. Starting with both jugs empty and aiming for 2 liters in A and 4 liters in B, the order below reaches the target state in 8 operations.

$(0,0)$ → F(B) → $(0,5)$ → M(B,A) → $(2,3)$ → E(A) → $(0,3)$ → M(B,A) → $(2,1)$ → E(A) → $(0,1)$ → M(B,A) → $(1,0)$ → F(B) → $(1,5)$ → M(B,A) → $(2,4)$

With this order, 5 operations are enough.

$(0,0)$ → F(A) → $(2,0)$ → M(A,B) → $(0,2)$ → F(A) → $(2,2)$ → M(A,B) → $(0,4)$ → F(A) → $(2,4)$

Given the two capacities and the target state, write a program that computes the minimum number of operations needed to reach the target state, starting with both jugs empty.

A single line on standard input contains the integers $a$, $b$, $c$, $d$, separated by spaces. $a$ is the capacity of jug A, $b$ is the capacity of jug B, $c$ is the amount that must remain in jug A in the target state, and $d$ is the amount that must remain in jug B in the target state. The bounds are $1 \le a < 100000$, $a < b \le 100000$, $0 \le c \le a$, $0 \le d \le b$.

Print on one line of standard output the minimum number of operations that reaches the target state. If no sequence of operations reaches the target state, print -1.