Problem D
Highest Tower

Oni loved to build tall towers of blocks. Her parents were not as amused though. They were on the verge of going crazy over that annoying loud noise whenever a tower fell to the ground, not to mention having to pick up blocks from the floor all the time. Oni’s mother one day had an idea. Instead of building the tower out of physical blocks, why couldn’t Oni construct a picture of a tower using two-dimensional rectangles that she montaged on a board on the wall? Oni’s mother cut out rectangles of various sizes and colors, drew a horizontal line representing the ground at the bottom of the board, and explained the rules of the game to Oni: every rectangle must be placed immediately above another rectangle or the ground line. For every rectangle you can choose which of its two orientations to use. I.e., if a rectangle has sides of length $s$ and $t$, you can either have a side of length $s$ horizontally or a side of length $t$ horizontally. You may place exactly one rectangle immediately above another one if its horizontal side is strictly smaller than the horizontal side of the rectangle beneath. Exactly one rectangle must be placed on the ground line. Now try to build as tall a tower as possible!

Oni’s mother took extra care to make sure that it was indeed possible to use all rectangles in a tower in order not to discourage Oni. But of course Oni quickly lost interest anyway and returned to her physical blocks. After all, what is the point of building a tower if you cannot feel the suspense before the inevitable collapse? Her father on the other hand got interested by his wife’s puzzle as he realized this is not a kids’ game.

Input

The first line of input contains an integer $n$ ($1 \le n \le 250\, 000$), the number of rectangles. Then follow $n$ lines, each containing two integers $s$ and $t$ ($1 \le s \le t \le 10^9$ nm), the dimensions of a rectangle.

You may safely assume that there is a way to build a tower using all $n$ rectangles.

Output

Output a single line containing the height in nm of the tallest possible tower using all the rectangles while having the horizontal side lengths strictly decreasing from bottom to top.

Sample Input 1	Sample Output 1
3 50000 160000 50000 100000 50000 100000	200000