题目描述

超市有一组促销商品集合 $Prod$。每售出一件商品 $x \in Prod$，超市将获得利润 $p_x$，且该商品必须在截止时间 $d_x$ 之前售出（$d_x$ 是一个整数时间单位，从销售开始时刻算起）。每件商品的销售恰好占用一个单位时间。一个销售计划是一个有序子集 $Sell \subseteq Prod$，其中每个商品 $x \in Sell$ 按照 $Sell$ 的顺序在截止时间 $d_x$ 或之前完成销售。销售计划的利润为 $Profit(Sell) = \sum_{x \in Sell} p_x$。最优销售计划是利润最大的销售计划。

例如，考虑商品集合 $Prod = \{a, b, c, d\}$，其中 $(p_a, d_a) = (50, 2)$，$(p_b, d_b) = (10, 1)$，$(p_c, d_c) = (20, 2)$，$(p_d, d_d) = (30, 1)$。可能的销售计划如表 1 所示。例如，销售计划 $Sell = \{d, a\}$ 表示商品 $d$ 的销售从时间 0 开始并在时间 1 结束，而商品 $a$ 的销售从时间 1 开始并在时间 2 结束。这些商品均在其截止时间前完成销售。$Sell$ 是最优销售计划，其利润为 80。

编写一个程序，从输入文本文件中读取多组商品数据，并计算每组商品的最优销售计划的利润。

输入

每组商品数据以一个整数 $0 \leq n \leq 10000$ 开头，表示该组商品的数量，随后是 $n$ 对整数 $p_i$ 和 $d_i$，其中 $1 \leq p_i \leq 10000$，$1 \leq d_i \leq 10000$，分别表示第 $i$ 件商品的利润和销售截止时间。输入数据中的空格可以自由出现。输入数据以文件结束符终止，且保证数据正确。

输出

对于每组商品数据，程序在标准输出中打印该组商品的最优销售计划的利润。每个结果从新的一行开始输出。

输入数据 1

4  50 2  10 1   20 2   30 1

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

输出数据 1

80
185

提示

样例输入包含两组商品数据。第一组数据对应表 1 中的商品。第二组数据包含 7 件商品，其最优销售计划的利润为 185

来源

2003年东南欧竞赛