뱀

가로와 세로 길이가 모두 $2L+1$인 정사각형 격자판이 있다. 각 칸은 좌표 $(x, y)$로 나타낸다. 가운데 칸은 $(0, 0)$, 맨 왼쪽 맨 아래 칸은 $(-L, -L)$, 맨 오른쪽 맨 위 칸은 $(L, L)$이다. $x$좌표는 왼쪽에서 오른쪽으로 갈수록, $y$좌표는 아래에서 위로 갈수록 커진다.

이 격자판의 $(0, 0)$ 칸에 뱀 한 마리가 자리를 잡고 있다. 처음에 뱀의 크기는 격자판 한 칸과 같고, 머리는 오른쪽을 바라본다. 뱀은 머리가 바라보는 방향으로 1초에 한 칸씩 몸을 늘리고, 머리는 새로 늘어난 칸으로 옮겨간다. 꼬리는 줄어들지 않으므로 몸이 지나간 칸은 그대로 남는다. 위 그림처럼 $L = 3$인 경우를 보자. 뱀은 처음에 $(0, 0)$에 있고, 크기는 한 칸이며, 머리는 오른쪽을 향한다. 1초가 지나면 몸이 한 칸 늘어나 $(0, 0)$과 $(1, 0)$ 두 칸을 차지하고, 머리는 $(1, 0)$에 놓인다. 1초가 더 지나면 $(0, 0)$, $(1, 0)$, $(2, 0)$ 세 칸을 차지하고, 머리는 $(2, 0)$에 놓인다.

뱀은 머리가 향한 방향을 정해진 규칙에 따라 시계방향 또는 반시계방향으로 90도 돌린다. 첫 번째 회전은 뱀이 출발한 지 $t_1$초 후에 일어나고, $i$($i > 1$)번째 회전은 $i-1$번째 회전이 끝난 뒤 $t_i$초 후에 일어난다. 즉 뱀은 $t_i$칸만큼 몸을 늘린 다음 머리를 돌리며, 머리를 돌리는 데에는 시간이 걸리지 않는다.

머리가 격자판 밖으로 나가거나 자기 몸이 있는 칸으로 들어가면 뱀은 그 즉시 숨을 거둔다. 숨을 거두기 직전까지는 몸을 계속 늘려나간다.

뱀이 머리를 돌리는 규칙, 즉 $t_i$와 그 방향이 주어졌을 때, 뱀이 출발한 지 몇 초 뒤에 숨을 거두는지 구하는 프로그램을 작성하라.

첫째 줄에 정수 $L$ ($1 \le L \le 10^8$)이 주어진다. 둘째 줄에 머리를 몇 번 돌리는지를 나타내는 정수 $N$ ($0 \le N \le 10^3$)이 주어진다. 다음 $N$개의 줄에 뱀이 머리를 어떻게 돌리는지에 대한 정보가 주어진다. $i$($1 \le i \le N$)번째 줄에 정수 $t_i$ ($1 \le t_i \le 2 \times 10^8$)와 $\mathrm{dir}_i$가 차례로 주어지며, $\mathrm{dir}_i$는 문자 L 또는 R이다. 뱀은 $i = 1$인 경우 출발한 지, 그 외의 경우엔 $i-1$번째 회전으로부터 $t_i$초 후에 $\mathrm{dir}_i$의 방향으로 머리를 돌린다. $\mathrm{dir}_i$가 L이면 왼쪽(반시계방향)으로, R이면 오른쪽(시계방향)으로 90도 돌린다.

첫째 줄에 뱀이 출발한 지 몇 초 후에 숨을 거두는지를 나타내는 값 하나를 출력한다.

첫 번째 예제에서는 출발한 지 7초가 지났을 때 머리가 자기 몸이 있는 $(1, 0)$ 칸으로 들어가고, 이때 뱀이 숨을 거둔다.