Grabbing Land

Time limit1sMemory limit128 MB

Summary

Split N rectangles into groups, each group costing the product of its max width and max height, minimizing the total cost.

Level: Hard8 of 10
Topics: Sorting, Dynamic programming, Greedy
Solved: No attempts yet

Problem

Farmer Sangheon wants to buy all $N$ plots of land from Seonjae's real estate. Each plot is a rectangle with width $W_i$ and height $H_i$ .

Normally a single plot costs $W_i \times H_i$ , but business has been slow, so Seonjae now offers the following bundle discount:

When several plots are bought together as one bundle, the price of that bundle is (the maximum $W_i$ among the plots in the bundle) $\times$ (the maximum $H_i$ among the plots in the bundle).

Sangheon will split the $N$ plots into one or more bundles and buy them all; every plot must belong to exactly one bundle. Because the total price depends on how the plots are grouped, find the minimum total cost to buy all of the plots.

Input

The first line contains the number of plots $N$ . ( $1 \le N \le 50000$ )

Each of the next $N$ lines contains the width $W_i$ and height $H_i$ of a plot, separated by a space. ( $1 \le W_i, H_i \le 1000000$ )

Output

Print the minimum total cost to buy all of the plots on a single line.

Hint

For example, with the four plots $(100, 1)$ , $(15, 15)$ , $(20, 5)$ , and $(1, 100)$ , you can split them into the three bundles $\{(100,1)\}$ , $\{(1,100)\}$ , and $\{(15,15),(20,5)\}$ . The cost is then $100 \times 1 + 1 \times 100 + 20 \times 15 = 500$ .

Examples5

Example 1
Input
```
4
100 1
15 15
20 5
1 100
```
Expected output
```
500
```
Example 2
Input
```
1
5 7
```
Expected output
```
35
```
Example 3
Input
```
2
3 3
5 5
```
Expected output
```
25
```
Example 4
Input
```
2
1000000 1
1 1000000
```
Expected output
```
2000000
```
Example 5
Input
```
1
1000000 1000000
```
Expected output
```
1000000000000
```