TSPMOHUG - Hu-Gi-Oh


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 ≤ 105)

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

p: power of the card (0 ≤ p ≤ 104)

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

n
p1 c2
p1 c2
...
pn cn

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.


hide comments
dpik: 2025-05-22 14:07:23

Example case explanation: If Hugo uses card one with a cooldown of 2, he cannot use card 2 AND 3 (p=2 and p=4)


Added by:OuiOuiBaguette
Date:2025-05-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All