408005 - 超市

一个超市有一个待售商品集合Prod，集合中每一个商品都有一个最晚销售时间，每一个产品都需要一个单独的单位时间销售（即两件商品不能同时销售），一个销售计划是一个有序子集Sell，Sell≤Prod，根据子集中的顺序，每一个商品都能在规定时间前销售出去。一个销售计划的利润则为Sell中的所有商品的利润和。 比如，如果Prod＝{a，b，c，d}，(pa，da)＝(50，2)，(pb，db)＝(10，1)，(pc，dc)＝(20，2)， (pd，dd)＝(30，1)，其中pi表示商品i的价值，di表示商品i的最晚销售时间。比如一个销售计划Sell＝{d，a}，d在0开始1时刻结束销售，a在1开始2时刻结束销售，所有商品都在规定时间前完成了销售，其利润为80，其他销售计划如表8.1所示。

表8.1 计划表 利润 {a} 50 {b} 10 {c} 20 {d} 30 {b，a} 60 {a，c} 70 {c，a} 70 {b，c} 30 {d，a} 80 {d，c} 50

写一个程序，来计算一个Prod的最大利润销售计划是多少利润。

一组数据以一个整数n（0≤n≤10 000）开始，接下来有n对pi，di（1≤pi≤10 000，1≤di≤10 000），数与数之间有空格隔开。

每组数据一行，输出最大利润是多少。