题目3--长方形盒子

Time Limit: 1000 ms Memory Limit: 131072 KiB

Problem Description

有n个长方形盒子,第i个长度为Li,宽度为Wi,我们需要把他们套放。注意一个盒子只可以套入长和宽分别不小于它的盒子,并且一个盒子里最多只能直接装入另外一个盒子(但是可以不断嵌套),例如1*1可以套入2*1,而2*1再套入2*2。套入之后盒子占地面积是最外面盒子的占地面积。给定N个盒子大小,求最终最小的总占地面积。

Input

第一行一个数N表示盒子的个数。
接下来N行,每行两个正整数,表示每个盒子的长度和宽度。
所有整数均在[1,200]区间内。

Output

一行一个整数表示最终最小的占地面积。

Sample Input

3
1 1
1 2
2 1

Sample Output

4

Hint


Source