问题描述

有 $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$ 个物品，找出你获得的最大总幸福值。

数据规模

$1\leq M\leq N\leq 2×10^5$

$T_i$ 为 0、1 或 2。

$1\leq X_i\leq 10^9$

所有输入值都是整数。

输入

输入来自标准输入，格式如下:

$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

如果您获得第 $1$ 件、第 $2$ 件、第 $5$ 件和第 $7$ 件物品，并使用第 $7$ 件物品（开罐器）打开第 $5$ 件物品，您将获得 $6+6+15=27$ 的愉快值。没有办法获得物品来获得 28 或更高的愉快值，但您仍然可以通过获得上述组合中的第 $6$ 个或第 $8$ 个物品而不是第 $7$ 个物品来获得 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