题目描述

一家超市有一组产品 $Prod$ 在出售。它为每个在截止时间 $dx$ 之前售出的产品 $x∈Prod$ 赚取利润 $px$，截止时间 $dx$ 是从销售开始时算起的整数单位时间。每件产品的销售恰好需要一个时间单位。

销售计划是一个有序的产品子集 $Sell ≤ Prod$，使得根据 $Sell$ 的顺序，每个产品 $x∈Sell$ 的销售在截止时间 $dx$ 之前或刚好在 $dx$ 到期时完成。销售计划的利润为 $Profit(Sell)=\sum_{x∈Sell}px$。最优销售计划是利润最大的计划。

例如，考虑产品 $Prod=\{a,b,c,d\}$，其中 $(pa,da)=(50,2)$，$(pb,db)=(10,1)$，$(pc,dc)=(20,2)$ 和 $(pd,dd)=(30,1)$。可能的销售计划列在上表中。例如，计划 $Sell=\{d,a\}$ 显示产品 $d$ 的销售从时间 $0$ 开始，到时间 $1$ 结束，而产品 $a$ 的销售从时间 $1$ 开始，到时间 $2$ 结束。这些产品都在其截止时间前售出。$Sell$ 是最优计划，其利润为 $80$。

输入格式

本题包含多组测试样例。

每组样例以整数 $0 <= n <= 10^4$ 开始，这是产品集的数量，然后是 $n$ 对整数 $pi,di$，$1 <= pi <= 10^4$和 $1 <= di <= 10^4$，分别表示第 $i$ 个产品的利润和销售截止时间。输入数据以文件结尾结束，并保证正确。

数据保证所有测试样例 $n$ 的总和不会超过 $10^4$。

输出格式

对于每个测试样例，程序打印出该组的最优销售计划的利润。每个结果从单独的一行开始打印。

样例

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