4402. [CCPC 2026 HA] 求求你不要再爬塔二了

Problem D. 求求你不要再爬塔二了

Input file: $\verb|standard input|$

Output file: $\verb|standard output|$

Asrit 正在玩杀戮尖塔二。他只剩 $1$ 滴血了，怪物即将攻击他，但是他抽到的手牌全都是攻击牌。

Asrit 有 $n$ 张手牌和 $m$ 点能量。每张手牌包含两个信息：耗能和伤害。耗能只有 $3$ 种可能：$\verb|1|$、$\verb|2|$ 或 $\verb|X|$。具体规则如下：

• 若一张手牌耗能为 $\verb|1|$，伤害为 $d$，则当剩余能量 $\ge 1$ 时可打出。打出后消耗 $1$ 点能量，造成 $d$ 点伤害。
• 若一张手牌耗能为 $\verb|2|$，伤害为 $d$，则当剩余能量 $\ge 2$ 时可打出。打出后消耗 $2$ 点能量，造成 $d$ 点伤害。
• 若一张手牌耗能为 $\verb|X|$，伤害为 $d$，则当剩余能量 $\ge 0$ 时可打出。打出后消耗当前所有的剩余能量，每消耗 $1$ 点能量造成 $d$ 点伤害（即总伤害为 $d \times$ 消耗能量数）。

Asrit 的游戏没有被瓦库接管，他可以以任意顺序打出任意满足条件的牌，且打出过的牌不会继续在手牌中。

请你告诉 Asrit，他的手牌最高能够打出多少伤害，以便他判断是否将会回到塔底。

Input

第一行输入两个整数 $n, m$ ($1 \le n \le 10^6, 1 \le m \le 2 \times 10^6$)，分别表示手牌数和初始能量数。

接下来 $n$ 行，每行输入一个字符 $op$ 和一个整数 $d$ ($op \in \{1, 2, X\}, 1 \le d \le 10^{12}$)，表示一张手牌的耗能类型和伤害。

Output

输出一行一个整数，表示能打出的最高伤害。

Examples

5 5
1 6
1 6
1 13
2 12
2 13

38

5 3
1 6
1 6
1 9
2 21
X 11

33