Indian National Olympiad in Informatics

Online Programming Contest, 10-11 June, 2006

IARCS home > OLYMPIAD

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 ≤ iN) is the deadline for the ith homework problem and the second integer on line i+1 is the number of bonus marks assigned to the ith 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



Copyright (c) IARCS 2003-2018;   Last Updated: 08 Aug 2006