This page is still under construction.

Parts of this page are still being built. What you see may change.

Valya and Letter

Time limit1sMemory limit512 MB

Summary
Given a sheet n by m and an envelope h by w, fold the sheet in half along either axis repeatedly so it fits (rotation allowed), minimizing folds.
Level

Medium6 of 10

Topics
Math, Greedy, Implementation, Binary search
Solved
No attempts yet

Problem

Valya got bored with social media, so she decided to write a good old handwritten letter to her friend. Valya wrote the letter on a rectangular sheet of paper. The sheet's dimensions are nn and mm cm. Then she found a rectangular envelope with dimensions hh and ww cm.

Unfortunately the letter could be too big to be placed into the envelope. So she might need to fold it several times. In one move Valya can fold the letter in half vertically or horizontally.

After folding the letter if necessary, Valya would put it into the envelope. Valya is a perfectionist, so she would always put the letter into the envelope in such way that its sides are parallel to the envelope's sides. The letter can be placed into the envelope if its corresponding dimensions don't exceed the envelope's dimensions. Before placing the letter Valya can rotate it by 9090 degrees. For example, if the letter's dimensions are equal to 1010 and 2020 cm, and the envelope's dimensions are equal to 2020 and 1010 cm, Valya doesn't need to fold the letter, she can rotate it by 9090 degrees to fit it into the envelope.

Valya doesn't want the letter to be crumpled so she wants to fold it the minimal possible number of times. Help her find this number.

Input

The first line of the input contains four integers nn, mm, hh and ww denoting the dimensions of the letter and dimensions of the envelope, respectively (1≤n,m,h,w≤10181 \leq n, m, h, w \leq 10^{18}).

Output

Output one number --- the minimal number of folds required, so that Valya could put the letter into the envelope.

Examples2

  1. Example 1

    Input
    10 20 20 10
    
    Expected output
    0
    
  2. Example 2

    Input
    3 3 2 2
    
    Expected output
    2