Asrit is playing Slay the Spire 2. He has only $1$ HP left, and the monster is about to attack him, but the hand he drew consists entirely of attack cards.

Asrit has $n$ cards in hand and $m$ energy points. Each card has two attributes: energy cost and damage. There are only $3$ possible energy costs: 1, 2, or X. The exact rules are as follows:

• If a card's energy cost is 1 and its damage is $d$, it can be played when the remaining energy is $\ge 1$. After playing it, $1$ energy is consumed and it deals $d$ damage.
• If a card's energy cost is 2 and its damage is $d$, it can be played when the remaining energy is $\ge 2$. After playing it, $2$ energy is consumed and it deals $d$ damage.
• If a card's energy cost is X and its damage is $d$, it can be played when the remaining energy is $> 0$. After playing it, all remaining energy is consumed, and each $1$ energy consumed deals $d$ damage (i.e., the total damage is $d \times \text{amount of consumed energy}$).

Asrit's game has not been taken over by Waku, so he can play any cards satisfying the conditions in any order, and cards that have already been played will no longer remain in his hand.

Please tell Asrit the maximum damage his hand can deal, so that he can determine whether he will return to the bottom of the Spire.

Input

The first line contains two integers $n, m$ $(1 \le n \le 10^6, 1 \le m \le 2 \times 10^6)$, representing the number of cards in hand and the initial energy.

The next $n$ lines each contain a character $op$ and an integer $d$ $(op \in \{\texttt{1}, \texttt{2}, \texttt{X}\}, 1 \le d \le 10^{12})$, representing a card's energy cost type and damage.

Output

Output a single line containing an integer, the maximum damage that can be dealt.

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