물고기 게임

당신은 물고기 게임을 한다. 당신은 더 작은 물고기를 먹는 물고기이지만, 더 큰 물고기에게 잡아먹혀서는 안 된다. 물고기의 크기는 변하지 않는다. 먹은 물고기마다 점수를 얻으며, 가능한 한 많은 점수를 얻고자 한다.

게임판은 $H$개의 행(1번부터 $H$번까지)으로 이루어진 격자이며, 열의 개수에는 제한이 없다. 당신은 $x=0$ 열에 있고 위아래로만 움직일 수 있다. 다른 물고기는 세로로 움직이지 않는다. 각 물고기는 $x>0$인 열에서 출발해 일정한 속도로 왼쪽, 즉 당신이 있는 열 방향으로 헤엄친다.

당신을 포함한 모든 물고기의 너비는 1칸이다. 당신의 높이는 7칸이다. 다른 물고기는 세 종류로, 작은 물고기는 높이 3, 중간 물고기는 높이 5, 큰 물고기는 높이 9이다. 물고기마다 속도가 다르다. 매 초마다 당신은 위로 한 칸, 아래로 한 칸 움직이거나 제자리에 머물 수 있다. 같은 시간 동안 작은 물고기는 1칸, 중간 물고기는 2칸, 큰 물고기는 3칸 왼쪽으로 이동한다. 시작 높이는 직접 고를 수 있지만, 물고기 전체가 게임판 안에 있어야 한다.

물고기는 자신보다 작은 물고기를 먹을 수 있다. 높이 3인 물고기를 먹으면 10점, 높이 5인 물고기를 먹으면 20점을 얻는다. 높이 9인 큰 물고기는 당신을 잡아먹으므로 피해야 한다. 잡아먹히면 게임에서 진다. 인어 아라시엘이 정한 규칙에 따라 매 초는 다음 순서로 진행된다.

1. 당신이 움직인다(위, 아래, 또는 제자리).
2. 큰 물고기는 3칸, 중간 물고기는 2칸, 작은 물고기는 1칸 앞으로 나아간다.
3. 큰 물고기는 같은 열에 있고 세로로 한 칸 이상 겹치는 중간 물고기, 작은 물고기, 당신을 먹는다.
4. 살아남은 중간 물고기는 같은 열에 있고 세로로 겹치는 작은 물고기를 먹는다.
5. 당신은 자신의 열($x=0$)에 있고 세로로 겹치는 작은 물고기와 중간 물고기를 먹는다.

첫 줄에 물고기의 수 $N$ ($1 \leq N \leq 50\,000$)과 게임판의 높이 $H$ ($20 \leq H \leq 1\,000$)이 주어진다.

이어서 $N$개의 줄에 물고기가 하나씩 주어진다. 각 줄은 종류를 나타내는 문자 L, M, S 중 하나(각각 작은, 중간, 큰 물고기)로 시작하고, 시작 열 $x$ ($2 \leq x \leq 10^{16}$), 물고기 가운데 칸의 행 $y$ 순서로 이어진다. 값은 공백으로 구분되며, $y$는 물고기 전체가 $[1, H]$ 안에 들어가도록 항상 주어진다.

입력은 다음 조건을 만족한다.

• 처음에 어떤 두 물고기도 완전히 또는 부분적으로 겹치지 않는다.
• 모든 $x$는 짝수이다. 큰 물고기의 $x$는 또한 3의 배수이다. 모든 충돌이 정수 좌표에서 일어나도록 하기 위해서이다.
• 당신이 잡아먹히지 않고 버티는 방법이 항상 존재한다.

득점의 최댓값을 나타내는 정수 하나를 한 줄에 출력한다. 최적으로 게임을 했을 때 얻는 점수이다.

그림 1은 첫 번째 예시의 상황이다. 실선 사각형은 물고기의 시작 위치이고, 점선 사각형은 4초와 8초 뒤의 위치이다. 검은 사각형은 당신의 여러 최적 시작 위치 중 하나이다. 이 경우 제자리에 머물며 초록색 중간 물고기를 기다리면 된다.

그림 2는 두 번째 예시의 상황이다. 검은 사각형은 $t=4$초에 파란색 작은 물고기를 먹을 때 당신이 있어야 하는 위치이고, 나뉜 칸은 두 물고기가 겹치는 칸이다. 그다음 전속력으로 위로 움직여 $t=11$에 초록색 중간 물고기를 먹는다. 마지막으로 $t=14$에 당신의 열에 도달하는 빨간색 큰 물고기를 피하려면 계속 위로 가야 한다.