购物

题目描述:

      dangline很喜欢购物，可是dangline是个穷比，一天只能买1个商品（每个商品都只有一个），超市里有n个商品。第i个的商品有P_i的价值，但也会在第D_i天过期，过期后的商品就不能买了。dangline想给自己买到最大的价值，请问最大的价值是多少？（假设dangline可以天天逛超市）。

输入格式:

      数据第一行是一个正整数n，表示商品数量（n<=20000），接下来一行包括2*n个正整数，第2*i-1个和第2*i个分别表示两个正整数P_i和D_i（0<P_i，D_i<=10000）表示价值和过期时间。

输出格式:

      数据输出一个正整数，即最大可获得的价值。

样例输入:

样例输入1：
4
50 2 10 1 20 2 30 1
样例输入2：
7
20 1 2 1 10 3 100 2 8 2 5 20 50 10

样例输出:

样例输出1：
80
样例输出2：
185

提示:

对于30%的数据，n<=500;P_i,D_i<=100;

对于60%的数据，n<=10000;P_i,D_i<=1000;

对于100%的数据，n<=20000;P_i,D_i<=10000;

第一组样例，第一天买30价值的，第二天买50价值的；

第二组样例，第一天买20价值的，第二天买100价值的，第三天买10价值的，第4到9天什么也不买，第10天买50价值的，第11到19天什么也不买，第20天买价值为5的。

本数据为zhr1502生成，未经版权许可，不得随意纂改！

时间限制: 1000ms
空间限制: 256MB

---

来源: by POJ 感谢zhr1502提供的翻译！