물통

용량이 서로 다른 빈 물통 A와 B가 하나씩 있다. 두 물통에 물을 채우고 비우는 작업을 반복해서 목표한 양의 물이 담긴 상태를 만들려고 한다. 물통 말고는 물의 양을 정확히 잴 방법이 없고, 할 수 있는 작업은 다음 세 가지뿐이다.

• F(x): 물통 x를 물로 가득 채운다. 채우기 전에 물통 x가 비어 있었는지는 상관없고, 다른 물통은 그대로 둔다.
• E(x): 물통 x에 담긴 물을 모두 버린다. 다른 물통은 그대로 둔다.
• M(x,y): 물통 x의 물을 물통 y에 붓는다. 물통 x에 남은 물의 양이 물통 y의 빈 공간보다 적거나 같으면 x의 물을 전부 y에 붓는다. 그보다 많으면 y가 가득 찰 때까지 붓고 나머지는 x에 남긴다.

표기 $(p,q)$는 물통 A에 $p$리터, 물통 B에 $q$리터가 담긴 상태를 뜻한다.

예를 들어 물통 A와 B의 용량이 각각 2리터와 5리터라고 하자. 두 물통이 모두 빈 상태에서 시작해 A에 2리터, B에 4리터를 남기려면 다음 순서로 작업해서 8번 만에 목표 상태에 도달한다.

$(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)$

작업 순서를 다음처럼 바꾸면 5번이면 충분하다.

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

두 물통의 용량과 목표 상태가 주어질 때, 두 물통이 모두 빈 상태에서 시작해 목표 상태에 도달하는 최소 작업 수를 구하는 프로그램을 작성하시오.

표준 입력 한 줄에 정수 $a$, $b$, $c$, $d$가 공백으로 구분되어 주어진다. $a$는 물통 A의 용량, $b$는 물통 B의 용량, $c$는 목표 상태에서 물통 A에 남아야 하는 물의 양, $d$는 목표 상태에서 물통 B에 남아야 하는 물의 양이다. $1 \le a < 100000$, $a < b \le 100000$, $0 \le c \le a$, $0 \le d \le b$이다.

목표 상태에 도달하는 최소 작업 수를 표준 출력에 한 줄로 출력한다. 목표 상태에 도달하는 방법이 없으면 -1을 출력한다.