AT_abc312_f [ABC312F] Cans and Openers

题目描述

有 $N$ 个物品。
这些物品分别属于以下三类之一：不需要开罐器的罐头、需要开罐器的罐头、开罐器。
第 $i$ 个物品由整数对 $(T_i, X_i)$ 表示，具体如下：

• 如果 $T_i = 0$，则第 $i$ 个物品是不需要开罐器的罐头，获得它可以获得 $X_i$ 的满足度。
• 如果 $T_i = 1$，则第 $i$ 个物品是需要开罐器的罐头，获得它并使用开罐器后可以获得 $X_i$ 的满足度。
• 如果 $T_i = 2$，则第 $i$ 个物品是开罐器，可以用于开启最多 $X_i$ 个罐头。

请你从 $N$ 个物品中选出 $M$ 个，求能够获得的满足度总和的最大值。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$T_1$ $X_1$
$T_2$ $X_2$
$\vdots$
$T_N$ $X_N$

输出格式

请输出一个整数，表示最大可能获得的满足度总和。

输入输出样例 #1

输入 #1

8 4
0 6
0 6
1 3
1 5
1 15
2 1
2 10
2 100

输出 #1

27

输入输出样例 #2

输入 #2

5 5
1 5
1 5
1 5
1 5
1 5

输出 #2

0

输入输出样例 #3

输入 #3

12 6
2 2
0 1
0 9
1 3
1 5
1 3
0 4
2 1
1 8
2 1
0 1
0 4

输出 #3

30

说明/提示

限制条件

• $1 \leq M \leq N \leq 2 \times 10^5$
• $T_i$ 取 $0, 1, 2$ 中的一个
• $1 \leq X_i \leq 10^9$
• 输入的所有值均为整数

样例解释 1

选择第 $1, 2, 5, 7$ 个物品，并用第 $7$ 个物品（开罐器）开启第 $5$ 个物品，可以获得满足度 $6 + 6 + 15 = 27$。不存在能获得满足度 $28$ 或以上的选法，在上述例子中，即使用第 $6$ 个物品或第 $8$ 个物品代替第 $7$ 个物品，也可以获得满足度 $27$。

由 ChatGPT 4.1 翻译