L. 求求你不要再爬塔二了
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

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

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

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

Input

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

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

Output

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

Examples
Input
5 5
1 6
1 6
1 13
2 12
2 13
Output
38
Input
5 3
1 6
1 6
1 9
2 21
X 11
Output
33