题目描述

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

输入的值都是整数。

输出格式

输出答案。

8 4

0 6

0 6

1 3

1 5

1 15

2 1

2 10

2 100

样例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 
【数据范围】 

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

$T_i$ 是 $0$，$1$ 或 $2$。

$1 \leq X_i \leq 10^9$

输入的值都是整数。 ```