题目描述

有 $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$ 的满意度。