Hugo Wangbros has been playing a lot of Yu-Gi-Oh recently, and he recently invented his own variation of the game: Hu-Gi-Oh!

In the world of Hu-Gi-Oh, Hugo is in a duel where he must build a power chain using a selection of magic cards. Each card has a power value and a cooldown time. Hugo wants to play cards in a sequence such that:

• He skips at least the number of rounds equal to the cooldown after using any card before using the next one.
• The total power is maximized.

Given a list of cards, each with its power and cooldown, compute the maximum power Hugo can achieve.

Note: Hugo is allowed to skip the card on any round.

Input

n: number of cards (1 ≤ n ≤ 10⁵)

n lines follow, each containing two integers p and c:

p: power of the card (0 ≤ p ≤ 10⁴)

c: cooldown of the card (0 ≤ c ≤ n)

n
p₁ c₂
p₁ c₂
...
p_n c_n

Output

output a single integer, the maximum total power Hugo can achieve.

Example

Input:
5
3 2
2 1
4 0
6 2
1 1

Output:
10

Explanation

The optimal solution is to first play card 3 (p=4, c=0), and play card 4 (p=6, c=2). Which gives 10.