Folding a Rectangle

Each fold reduces one side to max(x, L-x). Find the fewest folds to turn sides W, H into w, h, in any orientation, or report -1.

Medium6MathNumber theoryImplementationNo attempts yetTime limit2sMemory limit256 MB

Problem

You have a rectangular sheet of paper whose sides are WW and HH. You want to fold it several times until it becomes a rectangle whose sides are ww and hh.

Every fold line is parallel to a side of the rectangle, and the shape after a fold is again a rectangle. Folding a side of length LL at distance xx from one of its ends (0<x<L0 < x < L) leaves that side with the longer of the two pieces, max(x,Lx)\max(x, L-x), and the other side keeps its length.

The finished rectangle may be turned around. Any orientation whose sides are ww and hh counts.

Write a program that computes the minimum number of folds.

Input

The first line contains the two side lengths WW and HH of the starting rectangle. The second line contains the two side lengths ww and hh of the target rectangle. (1W,H,w,h1091 \le W, H, w, h \le 10^9)

Output

Print the minimum number of folds that turns the starting rectangle into the target rectangle. Print -1 when it is impossible.