Description
超市里有N个需要促销的商品,每个商品都有一个售卖截止日期dx,如果商品能够在对应的截止日期前(包含当天)卖掉,那么就能够获取到此商品对应的利润px。
注意一天只能够卖一个商品,不能同时卖多个。现在分别给出N个商品的利润及售卖截止日期,请计算出能够获取的利润的最大值
Input
输入包含多组测试数据。
对于每组测试数据,开头一个整数N(0≤N≤10000),表示商品的数量;接下来有N对数字,分别表示第i个商品的利润pi以及售卖截止日期di。1≤pi≤10000,1≤di≤ 10000,每个数字之间用一个或多个空格隔开
Output
对于每组测试数据,输出一行,输出能够获取的利润的最大值
4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10