当前没有测试数据。

题目描述

Rainbow 开了一家商店，在一次进货中获得了 $N$ 个商品。已知每个商品的利润和过期时间。Rainbow 每天只能卖一个商品，并且过期商品不能再卖。Rainbow 也可以选择在每天出售哪个商品，并且一定可以卖出。

由于这些限制，Rainbow 需要制定一份合理的售卖计划。请你计算一下，Rainbow 最终可以获得的最大收益。

输入格式

第一行两个整数 $N$。接下来 $N$ 行每行两个整数 $a_i, b_i$，分别表示每个商品的利润、过期时间。$1\le N,a_i,b_i\le 10000$。

输出格式

输出一个整数，表示 Rainbow 最终可以获得的最大收益。

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

185

第 $1$ 天卖出 $20$；第 $2$ 天卖出 $100$；第 $3$ 天卖出 $10$；第 $4$ 天卖出 $50$（实际上只要在第 $10$ 天卖就可以）；第 $5$ 天卖出 $5$（实际上只要在第 $20$ 天前卖就可以），总计 $185$。其它 $2$ 件商品由于过期、每天只能卖一个的限制，在最优策略下应该不出售。