该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P2949 [USACO09OPEN] Work Scheduling G

【题意】

为了维持农场的运转，约翰必须打工赚钱。

他接到了 $N$ 份工作，每份工作恰好占用他一天的时间。

约翰从第一天开始工作，他可以任意安排这些工作的顺序，第 $i$ 份工作有 $P_i$ 的报酬，但必须在第 $D_i$ 天结束之前完成。

在截止日期后完成的工作没有报酬。请帮助约翰规划每天的工作，使得他赚到的钱最多。

【输入格式】

第一行：单个整数 $N(1 \le N \le 10^6)$。

第二行到 $N + 1$ 行：第 $i + 1$ 行有两个整数：$Di$ 和 $Pi(1 \le D_i, P_i \le 10^9)$。

【输出格式】

单个整数，表示约翰最多可以赚多少钱。

【样例输入1】

3
2 10
1 5
1 7

【样例输出1】

17

【解释】

第一天做第三个工作，第二天做第一个工作。

【输入样例2】

7
1 6
1 7
3 2
3 1
2 4
2 5
6 1

【输出样例2】

15

【数据范围与提示】

对于 20% 的数据，$N \leq 10^3$；

对于 40% 的数据，$N \leq 10^4$；

对于 60% 的数据，$N \leq 10^5$；

对于 100% 的数据，$N \leq 10^6$，工作的完成期限均小于 $10^9$。