Asrit está jugando a 杀戮尖塔二. Solo le queda $1$ punto de vida y el monstruo está a punto de atacarlo, pero todas las cartas que ha robado son de ataque.

Asrit tiene $n$ cartas en la mano y $m$ puntos de energía. Cada carta contiene dos datos: su coste de energía y su daño. El coste solo tiene $3$ posibilidades: 1, 2 o X. Las reglas concretas son las siguientes:

• Si una carta tiene coste 1 y daño $d$, puede jugarse cuando la energía restante es $\ge 1$. Al jugarla, se consume $1$ punto de energía y se inflige $d$ de daño.
• Si una carta tiene coste 2 y daño $d$, puede jugarse cuando la energía restante es $\ge 2$. Al jugarla, se consumen $2$ puntos de energía y se inflige $d$ de daño.
• Si una carta tiene coste X y daño $d$, puede jugarse cuando la energía restante es $> 0$. Al jugarla, se consume toda la energía restante y se inflige $d$ de daño por cada $1$ punto de energía consumido (es decir, el daño total es $d \times \text{energía consumida}$).

La partida de Asrit no ha sido tomada por 瓦库. Puede jugar cualquier carta que cumpla las condiciones en cualquier orden, y las cartas jugadas dejan de estar en su mano.

Dile a Asrit cuál es el daño máximo que puede infligir con su mano, para que pueda determinar si volverá al fondo de la torre.

Entrada

La primera línea contiene dos enteros $n, m$ $(1 \le n \le 10^6, 1 \le m \le 2 \times 10^6)$, que indican, respectivamente, el número de cartas y la energía inicial.

Las siguientes $n$ líneas contienen, cada una, un carácter $op$ y un entero $d$ $(op \in \{\texttt{1}, \texttt{2}, \texttt{X}\}, 1 \le d \le 10^{12})$, que indican el tipo de coste de energía y el daño de una carta.

Salida

Imprime en una línea un entero que represente el daño máximo que se puede infligir.

Ejemplos

Entrada 1

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

Salida 1

38

Entrada 2

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

Salida 2

33