Asrit は 杀戮尖塔二 をプレイしています。HP は $1$ しか残っておらず、モンスターがまもなく攻撃してきますが、引いた手札はすべて攻撃カードです。

Asrit は $n$ 枚の手札と $m$ のエネルギーを持っています。各カードには、エネルギーコストとダメージという 2 つの情報があります。エネルギーコストは 1、2、X の $3$ 種類です。具体的なルールは次のとおりです:

• エネルギーコストが 1、ダメージが $d$ のカードは、残りのエネルギーが $\ge 1$ のときに使えます。使うとエネルギーを $1$ 消費し、$d$ のダメージを与えます。
• エネルギーコストが 2、ダメージが $d$ のカードは、残りのエネルギーが $\ge 2$ のときに使えます。使うとエネルギーを $2$ 消費し、$d$ のダメージを与えます。
• エネルギーコストが X、ダメージが $d$ のカードは、残りのエネルギーが $> 0$ のときに使えます。使うと現在残っているエネルギーをすべて消費し、エネルギーを $1$ 消費するごとに $d$ のダメージを与えます（つまり、合計ダメージは $d \times \text{消費したエネルギー数}$ です）。

Asrit のゲームは 瓦库 に乗っ取られていません。条件を満たすカードを任意の順序で使うことができ、使ったカードは手札には残りません。

Asrit が塔の底に戻ることになるかを判断できるように、手札で与えられるダメージの最大値を教えてください。

入力

最初の行には 2 つの整数 $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})$ が与えられ、1 枚のカードのエネルギーコストの種類とダメージを表します。

出力

与えられるダメージの最大値を表す整数を 1 個、1 行に出力してください。

入出力例

入力 1

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

出力 1

38

入力 2

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

出力 2

33