题目描述

本题译自 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

input

12 1
EENWSEEESWWS

output

3

图中的字是之前完整题面的，懒得改了。「市政厅」表示 $(0, 0)$，「散步路径」表示移动路线。 图我没有仔细 PS 过，可能对不齐、不对称，强迫症的同学们麻烦忍一忍

样例 2

input

12 2
EENWSEEESWWS

output

7

样例 2 与样例 1 的不同在于在样例 2 中 JOI 君走了两天。

样例 3

input

7 1
ENNWNNE

output

0

样例 4

input

16 5
WSESSSWWWEEENNNW

output

21

数据范围与提示

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