#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。