#3366. 超级市场 暂未评定

一家超市出售一套产品。在截止日期dx之前，它为每种产品x∈Prod赚取利润px，

该截止日期是从开始销售​​的那一刻起以时间单位的整数表示的。每种产品的销售时间正好是一个单位。销售进度表是产品Sell≤Prod的有序子集，

这样，根据Sell的顺序，每个产品x∈Sell的销售在截止日期dx之前或dx到期时完成。销售计划的利润为Profit（Sell）=Σx∈Sellpx。

最佳销售计划是利润最高的计划。例如，考虑产品Prod = {a，b，c，d}，其中（pa，da）=（50,2），（pb，db）=（10,1），（pc，dc）=（20 ，2）和（pd，dd）=（30,1）。

表1中列出了可能的销售时间表。

例如，时间表Sell = {d，a}显示产品d的销售在时间0开始并在时间1结束，而产品a的销售在时间1开始并在时间1开始。在时间2结束。这些产品在截止日期之前已售出。 卖出是最佳计划，其利润为80。

编写一个程序，该程序从输入文本文件中读取产品集，并为每组产品计算最佳销售计划的利润。

一组产品以整数0 <= n <= 10000开始，这是该组产品的数量。

然后以n对整数继续，即1 <= <= 10000和1 <= <= 10000，表示第i个产品的利润和销售截止日期。

输入中可以自由出现空格。输入数据以文件结尾终止，并保证正确。

对于每组产品，程序都会在标准输出上打印出该组最佳销售计划的利润。每个结果均从单独一行的开头打印。

样例输入

4  50 2  10 1   20 2   30 1

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

样例输出

80
185

样本输入包含两个产品集。第一组编码表1中的产品。第二组编码7种产品。这些产品的最佳计划利润是185。

POJ 1456