#9681. Summer Vacation

Summer Vacation

题目描述

There are NN one-off jobs available. If you take the ii-th job and complete it, you will earn the reward of BiB_i after AiA_i days from the day you do it.

You can take and complete at most one of these jobs in a day.

However, you cannot retake a job that you have already done.

Find the maximum total reward that you can earn no later than MM days from today.

You can already start working today.

NN 项一次性工作。如果你接受并完成 ii 项工作,那么从你完成工作的那一天起 AiA_i 天后,你将获得 BiB_i 的奖励。

您一天最多可以接受并完成其中一项工作。

但是,您不能重做已经完成的工作。

从今天起不迟于 MM 天,找出你能获得的最高总奖励。

您今天就可以开始工作。

输入格式

输入内容按以下格式标准输入:

NN MM
A1A_1 B1B_1
A2A_2 B2B_2
\vdots
ANA_N BNB_N

输出格式

打印从今天起不晚于 MM 天可以获得的最高奖励总额。

样例 #1

样例输入 #1

3 4
4 3
4 1
2 2

样例输出 #1

5

样例 #2

样例输入 #2

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

样例输出 #2

10

样例 #3

样例输入 #3

1 1
2 1

样例输出 #3

0

说明

数据规模与约定

  • 所有输入值均为整数。
  • 1N1051 \leq N \leq 10^5
  • 1M1051 \leq M \leq 10^5
  • 1Ai1051 \leq A_i \leq 10^5
  • 1Bi1041 \leq B_i \leq 10^4

样例 11 解释

通过完成以下工作,您可以获得总奖励 55

  • 今天接受并完成第一份工作。从今天起四天后,您将获得 33 的奖励。
  • 明天接受并完成第三项工作。从今天起两天后,即从今天起三天后,您将获得 22 的奖励。