题目名称

最优接单报酬规划

题目描述

存在 $n$ 份工作任务，若在截止日期前完成，可获得相应报酬。第 $i$ 份任务报酬为 $p_i$ ，需在第 $d_i$ 天结束前完成。每天仅能完成一份工作，且每份工作一天内可完成。需规划从第一天起每天执行的工作任务，使获得的总报酬最多。

输入格式

• 第一行：一个整数 $n$ ，代表工作任务的数量。
• 第二行至第 $n + 1$ 行：第 $i + 1$ 行包含两个整数 $d_i$ 和 $p_i$ ，分别为第 $i$ 份任务的截止日期和报酬。

输出格式

输出一个整数，即能获得的最大报酬。

数据范围

• 对于 50% 的数据，$1 \leq n \leq 3000$ 。
• 对于 100% 的数据，$1 \leq n \leq 300,000$ 。
• $1 \leq d_i \leq n$ 。
• $1 \leq p_i \leq 10^9$ 。

样例

输入

3
2 100
1 10
1 50

输出

150