RYIP在线题库
首 页   >   习题练习   >   提交
Problem2006--兼职

2006: 兼职

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

阿罗刚考上大学,他打算在这个暑假里勤工俭学,赚取一部分大学的学费,现在他有 n 份兼职工作,这些工作很灵活,他可以灵活安排每份工作什么时候去做,但是每份工作都需要占用他一天的时间去完成。其中第 i 份工作必须在第 di天结束之前完成,如果完成,可以获得 pi 的报酬,如果超过该期限,阿罗就无法拿到相应的报酬。

请你帮助阿罗规划一下,使得他赚到的钱尽可能多,并输出最多的报酬金额。


【 Input 】

第一行一个整数 n,接下来 n 行,每行有两个整数:di 和 pi,表示第 i 份工作的截止日期和报酬。

【 Output 】

输出一个整数,表示拓拓能拿到的最多的报酬。


【 Sample Input 】

3
2 100
1 10
1 50

【 Sample Output 】

150

【HINT】

· 对于 50% 的数据,1≤n≤3000

· 对于 100% 的数据,1≤n≤3×1051≤din1≤pi≤109

· 数据已加强(2023.8.7-lcj)


【 Source/Category 】

top TX