J7 习题-2 超市

题目描述

超市有一套产品在销售，产品 $x$ 在截止日期 $d_{x}$ 前售出时可以赚取 $p_{x}$ 的利润，$d_x$ 是从销售开始时计算的以天为单位的整数，每天只能选择一种产品进行销售，且每个产品仅能售出一次。求合理安排每天卖的产品的情况下，可以获得的最大利润。

例如，产品集合 $P=\left \{ a,b,c,d \right \}$ ，下面有几种销售计划：$(p_a,d_a)=(50,2)$， $(p_b,d_b)=(10,1)$ ，$(p_c,d_c)=(20,2)$ ，$(p_d,d_d)=(30,1)$。显然，最优的销售会是在第 $0$ 天到第 $1$ 天销售产品 $d$，然后在第 $1$ 天到第 $2$ 天销售产品 $a$，这个方案的利润是 $80$。

输入格式

输入包含多组测试数据 ：

每组数据的第一行为一个整数 $n$ ，代表这套产品中产品的数量

接下来为 $n$ 行，每行一对整数 $p_{i}$ $d_{i}$ ，分别表示该产品的利润和截止销售日期

输出格式

对于每组数据，输出该套产品的最大利润。

样例输入

4
50 2
10 1
20 2
30 1

样例输出

80

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据，$0 \le n \le 10000$，$1 \le p_{i} \le 10000$ 和 $1 \le d_{i} \le 1000$ 。