The Longest Welded Sword

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.

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.

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