阿罗刚考上大学,他打算在这个暑假里勤工俭学,赚取一部分大学的学费,现在他有 n 份兼职工作,这些工作很灵活,他可以灵活安排每份工作什么时候去做,但是每份工作都需要占用他一天的时间去完成。其中第 i 份工作必须在第 di天结束之前完成,如果完成,可以获得 pi 的报酬,如果超过该期限,阿罗就无法拿到相应的报酬。
请你帮助阿罗规划一下,使得他赚到的钱尽可能多,并输出最多的报酬金额。
第一行一个整数 n,接下来 n 行,每行有两个整数:di 和 pi,表示第 i 份工作的截止日期和报酬。
输出一个整数,表示拓拓能拿到的最多的报酬。
3
2 100
1 10
1 50
150
· 对于 50% 的数据,1≤n≤3000
· 对于 100% 的数据,1≤n≤3×105,1≤di≤n,1≤pi≤109
· 数据已加强(2023.8.7-lcj)