#355. 家庭作业

家庭作业

题目描述

老师在开学第一天就把所有作业都布置了,每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为 10\red{10},要求在 6\red{6} 天内交,那么要想拿到这 10\red{10} 学分,就必须在第 6\red{6} 天结束前交。

每个作业的完成时间都是只有一天。例如,假设有 7\red{7} 次作业的学分和完成时间如下:

作业号 期限 学分
1\red{1} 6\red{6}
2\red{2} 7\red{7}
3\red{3} 2\red{2}
4\red{4} 1\red{1}
5\red{5} 2\red{2} 4\red{4}
6\red{6} 5\red{5}
7\red{7} 6\red{6} 1\red{1}

最多可以获得 15\red{15} 学分,其中一个完成作业的次序为2,6,3,1,7,5,4\red {2,6,3,1,7,5,4},注意可能还有其他方法。

你的任务就是找到一个完成作业的顺序获得最大学分。

输入格式

第一行一个整数 N\red{N},表示作业的数量;

接下来 N\red{N} 行,每行包括两个整数,第一个整数表示作业的完成期限,第二个数表示该作业的学分。

输出格式

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

样例

输入样例

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

输出样例

15

提示

对于 20%\red{20\%} 的数据,N103\red{N \leq 10^3}

对于 40%\red{40\%} 的数据,N104\red{N \leq 10^4}

对于 60%\red{60\%} 的数据,N105\red{N \leq 10^5}

对于 100%\red{100\%} 的数据,N106\red{N \leq 10^6},作业的完成期限均小于 7×105\red{7\times 10^5}