Problem3002--超市促销

3002: 超市促销

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

超市里有N个需要促销的商品,每个商品都有一个售卖截止日期dx,如果商品能够在对应的截止日期前(包含当天)卖掉,那么就能够获取到此商品对应的利润px。
注意一天只能够卖一个商品,不能同时卖多个。现在分别给出N个商品的利润及售卖截止日期,请计算出能够获取的利润的最大值

Input

输入包含多组测试数据。
对于每组测试数据,开头一个整数N(0≤N≤10000),表示商品的数量;接下来有N对数字,分别表示第i个商品的利润pi以及售卖截止日期di。1≤pi≤10000,1≤di≤ 10000,每个数字之间用一个或多个空格隔开

Output

对于每组测试数据,输出一行,输出能够获取的利润的最大值

Sample Input Copy

4  50 2  10 1   20 2   30 1


7  20 1   2 1   10 3   100 2   8 2   5 20   50 10

Sample Output Copy

80
185

Source/Category

 level6