103125: [Atcoder]ABC312 F - Cans and Openers

Problem Statement

There are $N$ items.
Each of these is one of a pull-tab can, a regular can, or a can opener.
The $i$-th item is described by an integer pair $(T_i, X_i)$ as follows:

• If $T_i = 0$, the $i$-th item is a pull-tab can; if you obtain it, you get a happiness of $X_i$.
• If $T_i = 1$, the $i$-th item is a regular can; if you obtain it and use a can opener against it, you get a happiness of $X_i$.
• If $T_i = 2$, the $i$-th item is a can opener; it can be used against at most $X_i$ cans.

Find the maximum total happiness that you get by obtaining $M$ items out of $N$.

Constraints

• $1 \leq M \leq N \leq 2 \times 10^5$
• $T_i$ is $0$, $1$, or $2$.
• $1 \leq X_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$T_1$ $X_1$
$T_2$ $X_2$
$\vdots$
$T_N$ $X_N$

Output

Print the answer as an integer.

Sample Input 1

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

Sample Output 1

27

If you obtain the $1$-st, $2$-nd, $5$-th, and $7$-th items, and use the $7$-th item (a can opener) against the $5$-th item, you will get a happiness of $6 + 6 + 15 = 27$.
There are no ways to obtain items to get a happiness of $28$ or greater, but you can still get a happiness of $27$ by obtaining the $6$-th or $8$-th items instead of the $7$-th in the combination above.

Sample Input 2

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

Sample Output 2

0

Sample Input 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

Sample Output 3

30

问题描述

有N件物品。

• 如果$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 \times 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$

输出

打印答案作为整数。

样例输入1

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

样例输出1

27

如果你获取第1个，第2个，第5个和第7个物品，并对第5个物品（一个开罐器）使用第7个物品，你会得到幸福值$6 + 6 + 15 = 27$。

没有获取物品的方法可以获得幸福值为28或更大的方法，但是你仍然可以通过在上面的组合中获取第6个或第8个物品而不是第7个来获得幸福值27。

样例输入2

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

样例输出2

0

样例输入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