### Indian National Olympiad in Informatics

### Online Programming Contest, 10-11 June, 2006

### Advanced Division

Problem 2: Homework, *(K Narayan Kumar, CMI)*

A teacher assigns homework at the beginning of the first day
of class. Each homework problem carries one mark, plus a bonus
if submitted within a specified number of days. The deadline for
earning the bonus and the number of bonus marks are different for
each homework problem. For instance, if a problem has a deadline
of 6 days and carries bonus 10 marks, then it earns 10 bonus
marks provided it is submitted before the end of the 6th day.

Each homework problem takes exactly one day to complete. For
instance, suppose there are seven problems with deadlines and
bonuses as follows:

Problem number 1 2 3 4 5 6 7
Deadline for bonus 1 1 3 3 2 2 6
Bonus marks 6 7 2 1 4 5 1

The maximum number of bonus marks one can obtain is 15, which
can be achieved by completing the problems in the sequence
2,6,3,1,7,5,4. Note that there are also other sequences that
achieve the same effect.

Your task is to find a schedule to complete all homework problems
so as to maximize bonus marks. Input format

The first line contains an integer *N*, indicating the
number of homework problems. This is followed by *N*
lines (lines 2,…,*N*+1), each containing two
integers. The first integer on line *i*+1 (1 ≤
*i* ≤ *N*) is the deadline for the
*i*^{th} homework problem and the second integer
on line *i*+1 is the number of bonus marks assigned to the
*i*^{th} homework problem.

Output format

A single integer indicating the maximum number of bonus marks
that can be obtained.Test Data:

You may assume that 1 ≤ *N* ≤ 200000.

Example:

Here is the sample input and output corresponding to the example discussed
above.

Sample Input

7
1 6
1 7
3 2
3 1
2 4
2 5
6 1

Sample Output

15