Cutting Cake

Time Limit: 2 Seconds
Memory Limit: 65536 KB

Angel bought a cake for c.x of size N*M. And there are several cherries on
the cake, shown below:

We want to cut the cake into pieces. And rules showed below:

1) We must cut along the edge of the gird, and must cut the cake into two pieces.

2) Each part of the cake must have exact one cake.

3) If a part contains only one cake, we can use that piece, or we'll continue
cutting until each part have exact one cake.

For example:

The total cost (cut length) is 3+2=5.

Write a program to calculate the minimum cost.

**Input**

M N (1 <= M, N<= 10)

X1 Y1

X2 Y2

...

0 0

Proceed to the end of file.

**Output**

For each case, output an integer stands for the minimum cost.

**Sample Input**

3 4

2 4

1 2

3 2

0 0

**Sample Output**

5

Author:

**JIANG, Yanyan**
Source:

**JIANG, Yanyan's Contest #1**
Submit
Status