The Longest Welded Sword

Time limit7sMemory limit512 MB

Summary

Select and order all plates so that widths strictly decrease, orienting each plate to maximize the total contributed length sum.

Level: Hard8 of 10
Topics: Greedy, Sorting, Dynamic programming, Array
Solved: No attempts yet

Problem

A blacksmith builds one sword out of rectangular iron plates. The order has these conditions.

The plates are never cut. They are welded together in a single row.
Each plate uses one of its two sides as the width of the sword, and the remaining side adds its length to the sword.
The result has to look like a sword, so the width must keep shrinking along the row. No plate may be attached at a width that equals or exceeds the width of the plate before it.
All $n$ plates the blacksmith owns are used, with none left over.

The blacksmith picks the welding order and the orientation of every plate. The length of the sword is the sum of the sides that the plates contribute.

Find the length of the longest sword that can be built.

Input

The first line contains the number of plates $n$ . ( $1 \le n \le 250000$ )

Each of the next $n$ lines contains the two side lengths $s$ and $t$ of one plate, in nanometers. ( $1 \le s \le t \le 10^9$ )

Only inputs for which a sword using all $n$ plates exists are given.

Output

Print on the first line the length of the longest sword that uses all $n$ plates.

Examples3

Example 1

Input

3
50000 160000
50000 100000
50000 100000

Expected output

Example 2
Input
```
1
1 1000000000
```
Expected output
```
1000000000
```
Example 3
Input
```
3
2 10
2 20
2 30
```
Expected output
```
34
```