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