Cutting an L-shaped paper

Time limit2sMemory limit256 MB

Summary

The program cuts the given L-shaped sheet with guillotine cuts into integer-sided squares with the fewest pieces.

Level: Medium7 of 10
Topics: Dynamic programming, Geometry, Recursion
Solved: No attempts yet

Problem

You have one sheet of paper shaped like the letter L, and every side of it has a positive integer length. You want to cut the sheet several times so that every piece is a square whose side length is a positive integer.

The cutting rules are these.

A cut runs vertically or horizontally. Diagonal cuts are not allowed.
The blade cannot change direction in the middle of a cut.
The blade cannot stop in the middle of a cut. Once you start cutting a piece, you keep cutting until that piece separates into two pieces.
Every side of every piece must have a positive integer length.

In the figure below, the left drawing is a given sheet and the right drawing is the result of cutting it into the smallest possible number of squares under these rules.

An L-shaped sheet and a cut into the fewest squares

Write a program that cuts the given L-shaped sheet into squares under these rules with as few pieces as possible.

Input

The first line contains four integers $h_1$ , $w_1$ , $h_2$ , $w_2$ , separated by spaces, that give the side lengths of the L-shaped sheet. ( $2 \le h_1, w_1 \le 50$ , $1 \le h_2 < h_1$ , $1 \le w_2 < w_1$ )

The sheet is what is left after a rectangle of height $h_2$ and width $w_2$ is removed from one corner of a rectangle of height $h_1$ and width $w_1$ . The figure below shows which side each integer refers to.

The side that each integer refers to

Output

Print, on one line, the minimum number of pieces produced by cutting the given L-shaped sheet under the rules.

Examples3

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