블록 쌓기 시뮬레이션

너비 W인 블록 쌓기 보드에 H개의 블록을 순서대로 떨어뜨린다. 블록은 5종류이다.

• I: 1×4 세로 블록 (1칸 차지, 4칸 높이)
• O: 2×2 블록 (2칸 차지)
• L: 오른쪽 방향 L모양 (2칸 너비, 왼쪽 1칸 높이 2, 오른쪽 1칸 높이 1)
• J: 왼쪽 방향 J모양 (2칸 너비, 왼쪽 1칸 높이 1, 오른쪽 1칸 높이 2)
• T: 3칸 너비, 중앙 1칸이 1칸 더 위로 올라온 T 모양

각 블록을 지정된 열(가장 왼쪽 열 기준, 1-인덱스)에 떨어뜨린 후 최대 높이를 구하여라.

입력

첫째 줄에 W, H, 이후 H개의 줄에 블록 종류와 열 번호가 주어진다.

• 1 ≤ W ≤ 10
• 1 ≤ H ≤ 10,000
• 블록이 보드 밖으로 나가는 경우는 없다.

출력

H개의 블록을 모두 놓은 후 최대 높이를 출력한다.

예제 입력 1

5 3
I 1
O 2
I 1

예제 출력 1

8