Snake

A square board has width and height both equal to $2L+1$. Every cell is written as a coordinate pair $(x, y)$. The center cell is $(0, 0)$, the bottom left cell is $(-L, -L)$, and the top right cell is $(L, L)$. The $x$ coordinate grows from left to right and the $y$ coordinate grows from bottom to top.

One snake sits on cell $(0, 0)$ of this board. At the start the snake is the size of a single cell and its head faces right. Every second the snake extends its body by one cell in the direction the head faces, and the head moves into that new cell. The tail never retracts, so every cell the body has covered stays covered. Take the case $L = 3$ shown in the picture above. The snake starts on $(0, 0)$, is one cell in size, and its head faces right. After one second the body has grown by a cell and covers $(0, 0)$ and $(1, 0)$, with the head on $(1, 0)$. After one more second it covers $(0, 0)$, $(1, 0)$ and $(2, 0)$, with the head on $(2, 0)$.

The snake turns the direction its head faces by 90 degrees, clockwise or counterclockwise, on a fixed schedule. The first turn happens $t_1$ seconds after the snake starts, and turn $i$ (for $i > 1$) happens $t_i$ seconds after turn $i-1$ ends. So the snake extends its body by $t_i$ cells and then turns its head, and turning the head takes no time.

The snake dies the moment its head leaves the board or enters a cell its own body occupies. It keeps extending right up to that moment.

Given the turning schedule, that is each $t_i$ and its direction, write a program that reports how many seconds after the start the snake dies.

The first line has the integer $L$ ($1 \le L \le 10^8$). The second line has the integer $N$ ($0 \le N \le 10^3$), the number of times the head turns. Each of the next $N$ lines describes one turn. Line $i$ ($1 \le i \le N$) has the integer $t_i$ ($1 \le t_i \le 2 \times 10^8$) followed by $\mathrm{dir}_i$, which is the character L or R. The snake turns its head in direction $\mathrm{dir}_i$ at $t_i$ seconds after the start when $i = 1$, and at $t_i$ seconds after turn $i-1$ otherwise. An L turns the head 90 degrees to the left (counterclockwise) and an R turns it 90 degrees to the right (clockwise).

On the first line print one value, the number of seconds after the start at which the snake dies.

In the first sample the head enters $(1, 0)$, a cell its own body occupies, seven seconds after the start, and the snake dies there.