#P7036. Origami Folding

    ID: 20243 Type: Default 1000ms 256MiB

Origami Folding

Origami Folding

Alex loves origami. Initially mastering squares, she now is challenged by rectangles. Her goal is to determine the minimum possible number of folds required to transform a \(W \times H\) rectangle into a \(w \times h\) rectangle. Each fold must result in a rectangle, so only folds parallel to the sides are allowed.

Note that you are allowed to rotate the target rectangle. In other words, the transformation is possible if either \(w \le W\) and \(h \le H\), or \(w \le H\) and \(h \le W\).

The minimal number of folds required to reduce a dimension x to a target y (when \(x > y\)) can be computed as the minimum integer \(k\) satisfying

[ y\cdot2^k \ge x ]

If the current dimension is already at most the target, no fold is needed.

Your task is to output the minimum total number of folds required, or -1 if the transformation is impossible.

inputFormat

The input consists of a single line containing four space-separated integers:

  • W and H: the dimensions of the original rectangle,
  • w and h: the dimensions of the target rectangle.

It is guaranteed that all numbers are positive integers.

outputFormat

Output the minimum number of folds required to obtain the target rectangle. If the transformation is impossible, output -1.

sample

2 7 2 2
2