Summer Vacation

题目描述

有 $N$ 个一次性工作可供选择。如果你接受第 $i$ 个工作并完成，你将在你做该工作后 $A_i$ 天获得报酬 $B_i$。 你每天最多可以接受并完成一份工作。 但是，你不能重新接受已经做过的工作。 求在不晚于从今天算起 $M$ 天内你能获得的最大总报酬。 你可以从今天就开始工作。

输入格式

输入从标准输入按如下格式给出： $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

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

10

1 1
2 1

0

提示

输入中的所有数值都是整数。 $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$你可以按如下方式获得总报酬 $5$：

今天接受并完成第一个工作。你将在从今天起四天后获得报酬 $3$。 明天接受并完成第三个工作。你将在从明天起两天后获得报酬 $2$，也就是从今天起三天后获得报酬。

标签: AtCoder|abc137D

来源

AtCoder|abc137D