AT_abc137_d.[ABC137D] Summer Vacation
普及+/提高
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
有 N 个临时工兼职,第 i 个兼职如果接受并工作的话,将在 Ai 天后获得报酬 Bi。
你每天最多只能选择一个兼职去做,并且同一个兼职不能重复选择。
请你求出从今天起到 M 天后(包括第 M 天)能够获得的最大报酬总和。
注意,兼职可以从今天开始接受并工作。
输入格式
输入以如下格式从标准输入给出。
N M
A1 B1
A2 B2
⋮
AN BN
输出格式
请输出到 M 天后能够获得的最大报酬总和。
输入输出样例
输入#1
3 4 4 3 4 1 2 2
输出#1
5
输入#2
5 3 1 2 1 3 1 4 2 1 2 3
输出#2
10
输入#3
1 1 2 1
输出#3
0
说明/提示
限制条件
- 所有输入均为整数。
- 1≤N≤105
- 1≤M≤105
- 1≤Ai≤105
- 1≤Bi≤104
样例解释 1
如下选择兼职并工作时,报酬总和为 5,这是最大值。
- 今天,选择第 1 个兼职并工作,在今天起第 4 天后获得报酬 3。
- 明天(即今天起第 1 天后),选择第 3 个兼职并工作,在今天起 1+2=3 天后获得报酬 2。