Optimal Land Purchase

Farmer John is planning to expand his farm and is considering the purchase of \(N\) rectangular plots of land. If Farmer John buys a single plot, its price is equal to its area, i.e. the product of its length and width. However, he can choose to purchase a group of plots together. In that case, the price for the group is calculated as the product of the maximum length and the maximum width among the plots in the group. For example, grouping a \(3\times5\) plot with a \(5\times3\) plot costs \(5\times5=25\), which is cheaper than buying them separately (\(15+15=30\)).

Your task is to help Farmer John determine the minimum total cost required to purchase all the plots if he can partition them into one or more groups. All plots must be purchased exactly once and you can form groups arbitrarily.

inputFormat

The first line contains a single integer \(N\), representing the number of plots. Each of the following \(N\) lines contains two integers \(L\) and \(W\), representing the length and width of a plot, respectively.

outputFormat

Output a single integer which is the minimum total cost to purchase all the plots.

sample

2
3 5
5 3

25