Hobanwoo, who was fighting enemies in the Demon King's castle, decided to defeat them all at once by creating a meteor using a magic card that summons a meteorite, which he had previously obtained in the Starting Village.

Hobanwoo intends to fly as high as possible into the sky first, and then, using that position as the starting point, repeat the following action $N$ times using $N$ magic cards:

• Select one of the remaining magic cards.
• If the pair of positive integers written on the selected magic card is $a$ and $b$, ascend by $a$ to summon a meteorite, and then descend by $b$.
• The used magic card burns away and cannot be used again.

The power of the meteor completed by using $N$ cards is the sum of the heights of each meteorite from the ground. However, because Hobanwoo flew too high into the sky at the beginning, he could not calculate the power of the meteor!

Eventually, Hobanwoo decided to calculate the power of the meteor by considering the lowest point on the path from the starting point until all $N$ cards are used as the ground. It is said that when Hobanwoo flies up into the sky initially, he goes high enough that he cannot reach the ground regardless of the order in which he uses the $N$ cards.

Help Hobanwoo create the most powerful meteor possible by using the magic cards!

Input

The first line contains the number of magic cards, $N$. $(1 \le N \le 100\,000)$

From the second line, $N$ lines follow, each containing a pair of positive integers $a$ and $b$ written on each magic card, separated by a space. $(1 \le a, b \le 10^{9})$

Output

Output the maximum power of the meteor that can be created using the $N$ magic cards.