헬스장 걷기 기계의 한 칸

문제

헬스장에서 짧은 걷기 운동을 위한 기계를 시험하고 있다. 이 기계의 운동 기록은 길이가 같은 시간 칸 N개로 나뉜다. 기계에는 현재 속도 단계가 표시되며, 속도 단계는 0 이상 M 이하의 정수다. 운동을 시작하기 직전의 속도 단계는 0이다. 각 시간 칸의 시작에는 제어 명령 하나가 도착한다. 명령은 UP, DOWN, HOLD 중 하나다. UP은 속도 단계를 1 올리는 명령이고, DOWN은 속도 단계를 1 내리는 명령이며, HOLD는 현재 속도 단계를 유지하는 명령이다. 각 명령은 해당 시간 칸이 시작될 때 한 번만 적용한다. 속도 단계에는 상한과 하한이 있다. 현재 단계가 이미 M일 때 UP을 받아도 단계는 M으로 유지한다. 현재 단계가 이미 0일 때 DOWN을 받아도 단계는 0으로 유지한다. 경계를 넘기려는 명령을 받았다고 해서 기계가 멈추거나 다음 명령이 취소되는 일은 없다. 이후 명령도 원래 순서대로 처리한다. 기계는 명령을 먼저 적용한 다음, 바뀐 속도 단계로 그 시간 칸 동안 작동한다. 한 시간 칸에 기록되는 이동 거리는 명령 적용 후의 속도 단계와 같은 수의 거리 단위다. 예를 들어 명령을 적용한 뒤 단계가 3이면 그 칸에서 이동 거리 3을 기록한다. 단계가 0인 칸에서는 거리를 더하지 않지만, 그 시간 칸도 정상적으로 처리한 것으로 본다. 기록 담당자는 N개의 시간 칸에서 기록한 이동 거리를 모두 더하려 한다. 마지막 시간 칸의 명령도 먼저 적용하고 그 칸의 거리까지 더한 뒤 운동을 종료한다. 운동이 끝난 뒤의 속도 단계만으로 전체 거리를 계산할 수는 없으므로, 각 칸의 명령을 순서대로 반영해야 한다. 최대 속도 단계 M과 명령 목록이 주어질 때 전체 이동 거리를 구해야 한다.

입력

첫째 줄에 정수 N과 M이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 1,000
1 ≤ M ≤ 1,000
다음 N개 줄에 명령이 하나씩 주어진다. 각 명령은 UP, DOWN, HOLD 중 하나다.

출력

N개 시간 칸에서 기록한 전체 이동 거리를 정수 하나로 출력한다. 이동한 거리가 없으면 0을 출력한다.

6 2
UP
UP
UP
DOWN
HOLD
DOWN

7

4 3
DOWN
HOLD
DOWN
HOLD

0

5 1
UP
UP
DOWN
UP
HOLD

4

출처: Devin.KR 자체 제작