Problem Description

This problem is a translation from JOI 2016 Final T4「縄張り」

There is a Cartesian coordinate system. JOI is located at $(0, 0)$.
JOI follows a fixed program to move every day. This program consists of $N$ steps, described by a string $S$ of length $N$. The string consists only of uppercase letters $\texttt{E, N, W, S}$.
The $i$-th character $C_i (1\leqslant i\leqslant N)$ indicates where JOI will move. If JOI is at $(x, y)$ before step $i$:
* $C_i=\texttt{E}$: JOI will move to $(x+1, y)$;
* $C_i=\texttt{N}$: JOI will move to $(x, y+1)$;
* $C_i=\texttt{W}$: JOI will move to $(x-1, y)$;
* $C_i=\texttt{S}$: JOI will move to $(x, y-1)$.

The next day, JOI will start the program from the position where he stopped the previous day.
JOI will mark the point $(0, 0)$ and every point he reaches after each step. Initially, 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)$ are all marked at least once, the $1\times 1$ square with these four points as vertices belongs to JOI's territory.
How many territories does JOI have after $K$ days?

Input Format

The first line contains two integers $N, K$ separated by a space.
The second line contains a string $S$, representing the program of JOI's movement.

Output Format

An integer representing the number of territories JOI has.

Sample Input and Output

Sample Input #1

12 1
EENWSEEESWWS

Sample Output #1

3

Sample Input #2

12 2
EENWSEEESWWS

Sample Output #2

7

Sample Input #3

7 1
ENNWNNE

Sample Output #3

0

Sample Input #4

16 5
WSESSSWWWEEENNNW

Sample Output #4

21

Notes/Hints

Sample Explanation 1

The text in the image is from the original problem statement. "City Hall" represents $(0, 0)$, and "Walking Path" represents the movement route.
The image may not be perfectly aligned or symmetrical due to lack of precise editing. Please bear with it if you have OCD.

Sample Explanation 2

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

Data Range and Hints

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

见题面 Input 部分

见题面 Output 部分