409426: GYM103536 B Troubles

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Troublestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$$$).

ExampleInput
4
100 1
15 15
20 5
1 100
Output
500

加入题单

上一题 下一题 算法标签: