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

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

• 若一张手牌耗能为 1，伤害为 $d$，则当剩余能量 $\ge 1$ 时可打出。打出后消耗 $1$ 点能量，造成 $d$ 点伤害。
• 若一张手牌耗能为 2，伤害为 $d$，则当剩余能量 $\ge 2$ 时可打出。打出后消耗 $2$ 点能量，造成 $d$ 点伤害。
• 若一张手牌耗能为 X，伤害为 $d$，则当剩余能量 $> 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 1

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

Output 1

38

Input 2

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

Output 2

33