题目描述

一家超市有一组促销商品集合 $\text{Prod}$。每件商品 $x \in \text{Prod}$ 如果在其截止时间 $d_x$ 之前（含）售出，则能获得利润 $p_x$。这里的截止时间从销售开始时刻算起，以整数时间单位衡量。每件商品的销售恰好需要占用一个单位时间。

一个销售计划是商品集合 $\text{Prod}$ 的一个有序子集 $\text{Sell} \subseteq \text{Prod}$，使得按照 $\text{Sell}$ 中的顺序销售每一件商品 $x$ 时，销售完成的时间不晚于其截止时间 $d_x$。销售计划的利润为 $\text{Profit}(\text{Sell}) = \sum_{x \in \text{Sell}} p_x$。

最优销售计划是指利润最大的销售计划。

例如，考虑商品集合 $\text{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 所示。例如计划 $\text{Sell} = \{d,a\}$ 表示商品 $d$ 在时间 $0$ 开始销售，时间 $1$ 结束；商品 $a$ 在时间 $1$ 开始销售，时间 $2$ 结束。两件商品都在截止时间前售出。该计划是最优计划，利润为 $80$。

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

输入格式

每组数据以整数 $n$ 开始，表示该组商品的数量，满足 $0 \le n \le 10000$。

接下来有 $n$ 对整数 $p_i$ 和 $d_i$，表示第 $i$ 件商品的利润和销售截止时间，满足 $1 \le p_i \le 10000$，$1 \le d_i \le 10000$。

输入中可以有任意空白符。输入以文件结束符（EOF）终止，数据保证正确。

输出格式

对于每组商品，在标准输出中打印最优销售计划的利润。

每个结果独占一行，从行首开始。

样例

输入样例：

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

样例解释

样例输入包含两组商品。

• 第一组对应题目描述中的例子，最优利润为 $80$。
• 第二组包含 $7$ 件商品，最优利润为 $185$。

数据范围

• $0 \le n \le 10000$
• $1 \le p_i \le 10000$
• $1 \le d_i \le 10000$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB