Problem I: Rectangles

A factory produces rectangular sheets of metal of varying dimensions. In order to meet demand quickly, the factory has a very large collection of pre-fabricated sheets of different dimensions which are stored in a storeroom. You are the storekeeper and your task is to arrange the given sheets in the storeroom. The sheets must be placed horizontally along the floor but to save floor area, the sheets can be put on top of each other. However, to ensure stability, a sheet can be put on top of another only if it fits completely inside the sheet immediately below it. Moreover the centers of the two sheets must be vertically aligned and the sides must be parallel. A sheet may be rotated though about its center by 90 degrees to fit inside the lower sheet.

You have to write a program which will take the dimensions of the sheets as input and compute the minimum floor area required for storing the sheets, assuming that sheets can be stacked on top of each other as described above.

Input

The input consists of several test cases. The first line contains a single integer $n$ which is the number of sheets for this problem. If this is 0, it indicates end of input. Assume that $n$ is at most 200. The next $n$ lines contain two integers each, which are the dimensions of the $n$ sheets. There are no lines separating consecutive test cases.

Output

The output consists of the minimum floor space required for each test case, in the order in which they are given. There should be no leading spaces or lines separating different cases.

Sample Input

2
3 5
4 4
3
5 4
2 5
4 4
0

Sample Output

31
30