配点: 100 点
您生活在一个城市,许多道路南北延伸很长,许多道路东西延伸很长。彼此相邻 2 两条南北向道路之间的距离为 1 公里。还有,相邻的 2 两条东西向道路之间的距离也是 1 公里。
这个城市有市政厅。 1 有一个。市政厅所在的十字路口 表示为 (0, 0) 。这个城市的十字路口 使用 2 整数 i, j 的交叉点 表示为 (i, j) 。也就是说,交集(i, j) 表示交叉点。 从 (0, 0) 向东 i 公里(i < 0 向西 -i 公里),向北 j 公里(j < 0 向南 -j km) 表示高级位置处的交叉路口。
在市政厅里,有一个名叫乔伊的女孩。 1 我有两只狗。喜悦你 K 我制定了一天的步行计划。步行计划如下。
- K 第一天早上,乔伊过马路。 (0, 0) 。喜悦就在十字路口 标记 (0, 0) 。 除了(0, 0) 之外,没有任何由 Joy 标记的交叉点。
- K 每天中午散步。1 每天步行是 它由 N 步骤组成。在每一步中,从一个路口移动到下一个路口并标记目的地。无论哪天,乔伊每天中午的移动方式都是恒定的。
- 完成白天的旅程后,在当前所在的路口睡觉直到第二天早上。在市政厅 K 几天来,人们对乔伊通过行走创造的领地进行了很多讨论。4 交叉路口 Joy-kun 全部都是 (a, b), (a + 1, b), (a + 1, b + 1), (a, b + 1) 当标记超过 1 次时,4 两个路口围成的区域属于Joy的领地。
您已经创建了一个程序,可以根据 Joy 的行走计划计算属于 Joy 领地的地块数量。 决定这样做。
这座城市的道路很长,南北和东西方向都有足够的道路,乔伊走路永远不会到达道路边缘或城市边缘。
課題
给定 Joy 的行走计划,编写一个程序来计算属于 Joy 领土的地块数量。
入力
从标准输入读取以下输入。
- 1 在线 2 整数 写入 N, K 以空格作为分隔符。这就是每天的步行 N 次 步行计划由步骤组成。 K 代表持续数天。
- 2 线是长度
写入 N 字符串
给出 S 。字符串
从 S 左侧开始 p 文字目 (1 \leqq p \leqq N) 字符 C_p 是
它仅由
E,N,W,S。这些字符代表以下含义: 如果- 文字 C_p 是
在
E,那么 第p 步表示移动到东边相邻的路口。 第 - 文字 C_p 是
在
N,那么 第p 步表示向北移动到下一个路口。 第 - 文字 C_p 是
在
W,那么 第p 步表示移动到西边的相邻路口。 第 - 文字 C_p 是
在
S,那么 第p 步表示移动到南边旁边的路口。 在这里,交点(i, j),东、北、西、南的交点是 (i + 1, j),交差点 (i, j + 1),交差点 (i - 1, j),交差点 (i, j - 1) 。
- 文字 C_p 是
在
出力
属于 Joy 领土的部分数量被输出到标准输出。 1 行。
制限
所有输入数据满足以下条件。
- 1 \leqq N \leqq 100\,000.
- 1 \leqq K \leqq 1\,000\,000\,000.
小課題
小課題 1 [5 点]
满足以下条件。
- N \leqq 50.
- K = 1.
小課題 2 [10 点]
- K = 1 满意。
小課題 3 [23 点]
- N \leqq 50 满意。
小課題 4 [62 点]
没有其他限制。
入力例 1
12 1 EENWSEEESWWS
出力例 1
3
在此输入示例中,步行是 它将持续 1 天。1 当天,Joy从市政厅出发,移动如下图所示。
黑色圆圈是Joy已标记的路口,白色圆圈是Joy未标记的路口,双圆圈是与市政厅的路口,数字代表每一步。 在

入力例 1 中,下图阴影区域 3 部分属于 Joy 的领地。

入力例 2
12 2 EENWSEEESWWS
出力例 2
7
入力例 2 所以步行是 它将持续 2 天。每天的输入路径示例 与 1 相同。当行走完成后,下图中阴影区域所指示的区域 7 部分属于 Joy 的领地。

入力例 2 是一个小任务 1 和小作业 请注意,不满足 2 约束。 在
入力例 3
7 1 ENNWNNE
出力例 3
0
入力例 3 中,没有任何部分属于Joy的领土。
入力例 4
16 5 WSESSSWWWEEENNNW
出力例 4
21
入力例 4 是一个小任务 1 和小作业 请注意,不满足 2 约束。 在