# Problem G

Highest Tower

*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 |