D - 暑假

分数：400分

问题描述

有$N$份一次性工作可供选择。如果你接受第$i$份工作并完成它，将在从今天起$A_i$天后，也就是完成工作的那天赚取$B_i$的报酬。

你每天最多只能接受并完成一份工作。

然而，你不能重新完成已经完成过的工作。

找到在从今天起不晚于$M$天的情况下你可以获得的最大总报酬。

你可以从今天开始工作。

约束

• 输入中的所有值都是整数。
• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq A_i \leq 10^5$
• $1 \leq B_i \leq 10^4$

输入

输入的格式如下：

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

输出

输出你在从今天起不晚于$M$天的情况下可以获得的最大总报酬。

3 4
4 3
4 1
2 2

5

You can earn the total reward of $5$ by taking the jobs as follows:

• Take and complete the first job today. You will earn the reward of $3$ after four days from today.
• Take and complete the third job tomorrow. You will earn the reward of $2$ after two days from tomorrow, that is, after three days from today.

5 3
1 2
1 3
1 4
2 1
2 3

10

1 1
2 1

0