Cutting Cake

Time Limit: 1 Second    Memory Limit: 32768 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

Submit

Source: JIANG, Yanyan's Contest #1