「JOI 2016 Final」领地

题目描述

本题译自 JOI 2016 Final T4「縄張り」

有一个平面直角坐标系。JOI 君位于 $(0, 0)$ 。
JOI 君每天都按照一个固定的程序移动一轮。该程序有 $N$ 个步骤，用一个长度为 $N$ 的字符串 $S$ 描述。这个字符串仅由大写字母 $\texttt{E, N, W, S}$ 构成。
左数第 $i$ 个字符 $C_i (1\leqslant i\leqslant N)$ 表示 JOI 君会移动到哪里。如果在执行步骤 $i$ 前，JOI 君位于 $(x, y)$：

• $C_i=\texttt{E}$：JOI 君将移动到 $(x+1,y)$；
• $C_i=\texttt{N}$：JOI 君将移动到 $(x,y+1)$；
• $C_i=\texttt{W}$：JOI 君将移动到 $(x-1,y)$；
• $C_i=\texttt{S}$：JOI 君将移动到 $(x,y-1)$。

次日 JOI 君会从他前一天停止的位置开始执行程序。
JOI 君会把 $(0, 0)$ 以及每个步骤结束后到达的点作标记。开始时 JOI 君没有标记任何点。$K$ 天后，对于任意整数 $a, b$，如果 $(a,b),$ $(a+1,b),$ $(a,b+1),$ $(a+1,b+1)$ 这四个点都被标记了一次或以上，以这四个点为顶点的 $1\times 1$ 的正方形就属于 JOI 君的领地。
请问 $K$ 天后，JOI 君有多少个领地。

输入格式

第一行有两个整数 $N, K$，用空格分隔。
第二行有一个字符串 $S$，表示 JOI 君移动的程序。

输出格式

一个整数，表示 JOI 君有多少个领地。

样例 1

样例 1

输入

12 1
EENWSEEESWWS

输出

3

样例 2

样例 2

输入

12 2
EENWSEEESWWS

输出

7

样例 3

样例 3

输入

7 1
ENNWNNE

输出

0

样例 4

样例 4

输入

16 5
WSESSSWWWEEENNNW

输出

21

数据范围与提示

对于所有数据，$1\leqslant N\leqslant 10^5, 1\leqslant K\leqslant 10^9$。

Subtask #	特殊限制	分值
1	$N\leqslant 50, K = 1$	5
2	$K = 1$	10
3	$N\leqslant 50$	23
4	无	62