Problem1008--「一本通 1.1 练习 4」家庭作业

1008: 「一本通 1.1 练习 4」家庭作业

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

老师在开学第一天就把所有作业都布置了,每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为 101010,要求在 666 天内交,那么要想拿到这 101010 学分,就必须在第 666 天结束前交。
每个作业的完成时间都是只有一天。例如,假设有 7 次作业的学分和完成时间如下:
作业号 期限 学分
111 111 666
222 111 777
333 333 222
444 333 111
555 222 444
666 222 555
777 666 111
最多可以获得 151515 学分,其中一个完成作业的次序为 2,6,3,1,7,5,42,6,3,1,7,5,42,6,3,1,7,5,4,注意可能还有其他方法。
你的任务就是找到一个完成作业的顺序获得最大学分。

Input

第一行一个整数 NNN,表示作业的数量;
接下来 NNN 行,每行包括两个整数,第一个整数表示作业的完成期限,第二个数表示该作业的学分。

Output

输出一个整数表示可以获得的最大学分。保证答案不超过C/C++的int范围。

Sample Input

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

Sample Output

15

HINT

对于 20%20\%20% 的数据,N≤103N \leq 10^3N103
对于 40%40\%40% 的数据,N≤104N \leq 10^4N104
对于 60%60\%60% 的数据,N≤105N \leq 10^5N105
对于 100%100\%100% 的数据,N≤106N \leq 10^6N106,作业的完成期限均小于 7×1057\times 10^57×105

Source/Category


Submit Status