Problem Description

This problem is translated from JOI 2016 Final T4 “縄張り”.

There is a Cartesian coordinate plane. JOI is at $(0, 0)$.
Every day, JOI follows a fixed procedure and makes one round of moves. The procedure has $N$ steps and is described by a string $S$ of length $N$. This string consists only of the uppercase letters $\texttt{E, N, W, S}$.
The $i$-th character from the left, $C_i\ (1\leqslant i\leqslant N)$, indicates where JOI will move. If before executing step $i$, JOI is at $(x, y)$:

• If $C_i=\texttt{E}$, JOI moves to $(x+1,y)$.
• If $C_i=\texttt{N}$, JOI moves to $(x,y+1)$.
• If $C_i=\texttt{W}$, JOI moves to $(x-1,y)$.
• If $C_i=\texttt{S}$, JOI moves to $(x,y-1)$.

On the next day, JOI starts executing the procedure from where he stopped the previous day.
JOI marks $(0, 0)$ and every point he reaches after finishing each step. At the beginning, JOI has not marked any points. After $K$ days, for any integers $a, b$, if the four points $(a,b)$, $(a+1,b)$, $(a,b+1)$, $(a+1,b+1)$ have each been marked at least once, then the $1\times 1$ square with these four points as vertices belongs to JOI’s territory.
Find how many territories JOI has after $K$ days.

Input Format

The first line contains two integers $N, K$, separated by spaces.
The second line contains a string $S$, representing JOI’s movement procedure.

Output Format

Output one integer, the number of territories JOI has.

12 1
EENWSEEESWWS

3

12 2
EENWSEEESWWS

7

7 1
ENNWNNE

0

16 5
WSESSSWWWEEENNNW

21

Hint

Sample Explanation 1

The text in the figure is from the previous full statement, and I was too lazy to modify it. “市政厅” means $(0, 0)$, and “散步路径” means the movement path.
I did not carefully edit the image, so it may be misaligned or not symmetric. Please bear with it.

Sample Explanation 2

The difference between Sample 2 and Sample 1 is that in Sample 2, JOI walked for two days.

Constraints and Hints

For all testdata, $1\leqslant N\leqslant 10^5$, $1\leqslant K\leqslant 10^9$.

Translated by ChatGPT 5