A7610. [ABC137D] Summer Vacation
编程题
普及+/提高
知识点
题目描述
有 $N$ 个临时工兼职，第 $i$ 个兼职如果接受并工作的话，将在 $A_i$ 天后获得报酬 $B_i$。
你每天最多只能选择一个兼职去做，并且同一个兼职不能重复选择。
请你求出从今天起到 $M$ 天后（包括第 $M$ 天）能够获得的最大报酬总和。
注意，兼职可以从今天开始接受并工作。
你每天最多只能选择一个兼职去做，并且同一个兼职不能重复选择。
请你求出从今天起到 $M$ 天后（包括第 $M$ 天）能够获得的最大报酬总和。
注意，兼职可以从今天开始接受并工作。
输入格式
输入以如下格式从标准输入给出。
> $N$ $M$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_N$ $B_N$
> $N$ $M$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_N$ $B_N$
输出格式
请输出到 $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 \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$
### 样例解释 1
如下选择兼职并工作时，报酬总和为 $5$，这是最大值。
- 今天，选择第 $1$ 个兼职并工作，在今天起第 $4$ 天后获得报酬 $3$。
- 明天（即今天起第 $1$ 天后），选择第 $3$ 个兼职并工作，在今天起 $1+2=3$ 天后获得报酬 $2$。
- 所有输入均为整数。
- $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$
### 样例解释 1
如下选择兼职并工作时，报酬总和为 $5$，这是最大值。
- 今天，选择第 $1$ 个兼职并工作，在今天起第 $4$ 天后获得报酬 $3$。
- 明天（即今天起第 $1$ 天后），选择第 $3$ 个兼职并工作，在今天起 $1+2=3$ 天后获得报酬 $2$。