Asrit는 杀戮尖塔二를 플레이하고 있다. 남은 HP는 $1$뿐이고 몬스터가 곧 공격하려 하는데, 뽑은 손패는 모두 공격 카드이다.

Asrit에게는 손패 $n$장과 에너지 $m$이 있다. 각 카드에는 에너지 비용과 피해량이라는 두 정보가 있다. 에너지 비용은 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가 손패로 줄 수 있는 피해량의 최댓값을 알려 주어, 그가 탑의 바닥으로 돌아가게 될지 판단할 수 있도록 하라.

입력

첫 번째 줄에는 두 정수 $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

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