#P997. 游戏通关
游戏通关
背景
机房里的人都十分认真地在编程,但总有一些人会偷偷玩游戏。。。。。。
问题描述
XY经常在机房里偷偷玩游戏,于是他也经常被CJH教练批评。但屡次的批评一点作用也没有,你看他又开始玩起了游戏。
这次XY可碰上难题了,因为据可靠的线报CJH教练在不久后就回来机房,但XY需要完成N个任务才能将这个游戏通关。
每个任务完成时限T,就是这个任务必须在时间T之前完成(你可以认为游戏刚开始的时间为1),还有完成这个任务XY可以获得一定的奖励W。由于XY娴熟的技术以及任务的简单,他可以在一个单位时间将任务完成。
XY想要在CJH教练到来之前将任务全部完成,同时他也想获得最多的奖励。这个他本来可以编程自己完成的,但是为了能马上将游戏通关,他需要全神贯注进去。于是他没有空编程计算,于是他希望你能帮助他将问题的答案计算出来。
输入格式game.in
输入数据第一行有一个整数N,表示需要完成的任务数目;
接下来N行,每行两个整数T,W(中间用一个空格隔开),分别表示完成这个任务的最后期限和完成这个任务后获得的奖励。
输出格式game.out
输出数据有且仅有一行,只包含一个整数S,表示最多获得的奖励。
样例输入输出
2
1 5
1 4
5
5
2 3
1 2
4 5
1 3
3 4
15
样例解释
对于样例2 XY可以选择完成任务1,3,4和5,这样他可以获得奖励15。
数据规模
对于10%的数据,N≤100,Ti≤100,Wi≤2000;
对于30%的数据,N≤1000,Ti≤5000,Wi≤2000;
对于50%的数据,N≤10000,Ti≤20000,Wi≤2000;
对于100%的数据,N≤200000,Ti≤200000,Wi≤2000。