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

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