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 \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 翻译