Folding a Rectangle

Time limit2sMemory limit256 MB

Summary

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.

Level: Medium6 of 10
Topics: Math, Number theory, Implementation
Solved: No attempts yet

Problem

You have a rectangular sheet of paper whose sides are $W$ and $H$ . You want to fold it several times until it becomes a rectangle whose sides are $w$ and $h$ .

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 $L$ at distance $x$ from one of its ends ( $0 < x < L$ ) leaves that side with the longer of the two pieces, $\max(x, L-x)$ , and the other side keeps its length.

The finished rectangle may be turned around. Any orientation whose sides are $w$ and $h$ counts.

Write a program that computes the minimum number of folds.

Input

The first line contains the two side lengths $W$ and $H$ of the starting rectangle. The second line contains the two side lengths $w$ and $h$ of the target rectangle. ( $1 \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.

Examples3

Example 1
Input
```
2 7
2 2
```
Expected output
```
2
```
Example 2
Input
```
10 6
4 8
```
Expected output
```
2
```
Example 3
Input
```
5 5
1 6
```
Expected output
```
-1
```