409426: GYM103536 B Troubles

Peter has found a litter of $$$N$$$ kittens lying around in an alley somewhere and wants to give them up for adoption. However, kittens are trouble, they knock over your ornaments, dirty your house, etc. Luckily, Peter has found a way to measure how much trouble a group of kittens will cause.

Peter first identifies each kitten with two attributes, a naughtiness level $$$A_i$$$ and a cuteness level $$$B_i$$$. If he sends a particular group of cats to one owner, the trouble they will cause is given by the formula $$$\max(A_i) \cdot \max(B_i)$$$ over the group of kittens.

Peter wants to minimize the total trouble caused by these kittens by grouping them optimally and sending them to their new owners in those groups. Help Peter find out what this minimum total trouble is.

The first line of input contains one integer, $$$N$$$ ($$$1 \leq N \leq 300000$$$).

The next $$$N$$$ lines of input contains two integers each, $$$A_i$$$ and $$$B_i$$$ ($$$1 \leq A_i,B_i \leq 1000000$$$).

4
100 1
15 15
20 5
1 100

500