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$

输出格式

输出一个整数，表示答案。

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

27

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

0

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

30

提示

$1 \leq M \leq N \leq 2 \times 10^5$
$T_i$ 为 $0$、$1$ 或 $2$。
$1 \leq X_i \leq 10^9$
所有输入值均为整数。如果你获得第 $1$、$2$、$5$、$7$ 件物品，并用第 $7$ 件物品（一个开罐器）对第 $5$ 件物品使用，你会得到幸福值 $6 + 6 + 15 = 27$。
不存在获得幸福值 $28$ 或更高的方式，但你也可以通过在上述组合中将第 $7$ 件替换为第 $6$ 或第 $8$ 件来仍然得到 $27$。

标签: AtCoder|abc312F

来源

AtCoder|abc312F