罐头与开罐器

题目描述

有 $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

如果取得第 $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

数据范围

• $1 \le M \le N \le 2 \times 10^5$
• $T_i$ 为 $0$、$1$ 或 $2$。
• $1 \le X_i \le 10^9$
• 所有输入值均为整数。