24468번 - 충돌의 수

문제

길이가 $L$인 상자가 있다. 이 안에 크기를 무시할 수 있을 만큼 작은 공 $N$개가 존재한다. 길이가 $L$인 상자는 길이가 1ドル$인 구간 $L$개로 분할할 수 있으며, 모든 공은 구간과 구간 사이의 경계에서 운동을 시작한다. 모든 공들은 1ドル$초에 한 칸씩 움직인다. 만약 어떤 공이 벽이나 다른 공에 충돌한다면, 즉시 운동 방향이 반대로 바뀐다. 이때 공의 속력은 바뀌지 않는다. 또한 처음에 임의의 두 공 사이 간격은 짝수이고, 한 위치엔 하나의 공만 존재한다.

예를 들어, 위 그림은 $L=8$일 때를 나타낸 것이다. 시간 $t=0$일 때 빨간색 공은 처음 위치 1ドル$에서 오른쪽으로 이동하고 있고, 파란 공은 처음 위치 5ドル$에서 왼쪽으로 운동하고 있다. $t=2$일 때 두 공은 충돌하여 즉시 운동 방향이 반대로 바뀌게 된다.

$N$개의 공들의 처음 위치와 처음 운동 방향이 주어질 때, 시간 $T$초까지 공끼리 몇 번 충돌하는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 세 정수 상자의 길이 $L,ドル 공의 개수 $N,ドル 시간 $T$가 공백으로 구분되어 주어진다. $(5 \le L \le 1,000,円\ 2 \le N \le 100,\ 1 \le T \le 1,000円)$

두 번째 줄부터 $N$개 줄의 $i$번째 줄에는 $i$번째 공의 위치를 의미하는 정수 $S_i$와 방향 $C_i$가 공백으로 구분되어 주어진다. $(1 \le S_i < L,\ C_i \in \{\texttt{L}, \texttt{R}\})$

여기서 공의 위치란, 상자의 왼쪽으로부터 공까지의 거리이다.

출력

공들이 서로 충돌하는 횟수를 출력한다. $T$초일 때 공이 서로 충돌하는 경우도 포함하여 센다.

제한

힌트