Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2078
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.


M N (1 <= M, N<= 10)
X1 Y1
X2 Y2
0 0

Proceed to the end of file.


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


Author: JIANG, Yanyan
Source: JIANG, Yanyan's Contest #1
Submit    Status