题目内容

热门手游Y又迎来了大版本更新了，这次出了新的副本。这次副本中新增了 $N$ 个任务，每一个任务都需要花费一个单位时间，每个任务都有自己的截至时间和获得固定的佣金。

塔子哥从 $1$ 时刻开始开启副本，将持续在线玩 $10^{9}$个单位时间。在任一时刻，塔子哥都可以选择编号 $1$ 到 $N$ 的 $N$ 个任务中的任意一个任务来完成。 由于塔子哥在每个单位时间里只能做 $1$ 个任务，而每个任务都有一个截止日期。所以塔子哥可能不得不放弃一些任务来尽可能地获得最大的佣金。

对于第 $i$ 个任务，有一个截止时间$D_i$，如果塔子哥可以完成这个订单，那么他可以获的 $P_i$ 个佣金。 塔子哥想尽可能地获取更多的佣金来购买更高级的装备，那么塔子哥该选择做哪些任务才能得到更多的佣金呢？

输入描述

第 $1$ 行包含一个整数 $N$。 ($1$ <= $N$ <= $5 \times 10^{5}$)

接下来有 $N$ 行，每行包含两个以空格分隔的整数$D_i$和$P_i$ 。($1$ <= $D_i$ $<=$$10^{9}$，$1$ <= $P_i$ $<=$$10^{9}$)

输出描述

一行，包含一个整数，表示塔子哥所能拿到的最多佣金。

样例1

输入

4
2 10
1 5
1 7
3 20

输出

37

说明

Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 and complete job 4 (3,20) at time 3 to maximize the earnings (7 + 10 + 20 -> 37).

样例2

输入

5
2 2
4 3
1 1
3 2
3 2

输出

9

思路：贪心

把题目转换成卖n件商品 每件商品的过期时间为d 怎么卖可以使得利益最大化?

首先，我们可以将商品按照过期时间进行升序排列，然后我们可以按顺序去枚举每一件商品是否选择，整个选择的过程可以使用小根堆这个数据结构来维护 小根堆的size不会超多当前的过期日期(如果超过了，就需要考虑当前商品的价格和小根堆的top元素大小）然后根据大小进行调整 最后把小根堆中的价格累加即可

代码