题目背景

译自 ROI 2014 Day1 T2. Робинзон и крокодилы

题目描述

鲁滨逊住在一个由 $n \times m$ 个方格组成的矩形小岛上。

有几只鳄鱼爬上了岛，在阳光下取暖并打起了盹。鲁滨逊想要在不惊动它们的情况下，把这些讨厌的邻居赶回水里。为此，他向正在打盹的鳄鱼们扔坚果。

岛上的每个格子中至多有一只鳄鱼。被坚果惊吓到的鳄鱼会沿着固定方向笔直奔跑，直到冲进水里为止。对于每只鳄鱼，已知它被吓到后奔跑的方向。鳄鱼的奔跑方向始终与岛的边界平行。

如果一只受惊的鳄鱼在奔跑途中撞上了另一只鳄鱼，两只鳄鱼都会被激怒，并立刻攻击鲁滨逊。因此，鲁滨逊必须谨慎选择投掷坚果的目标，确保被吓跑的鳄鱼前方的所有格子都是空的。

鲁滨逊在一只鳄鱼完全跑进水里之前，不会再扔下一颗新的坚果。

请你编写程序，计算鲁滨逊最多可以赶走多少只鳄鱼，而不会激怒它们。

输入格式

第一行包含两个整数 $n$ 和 $m$ —— 分别表示岛的南北方向和东西方向的格子数量。

接下来的 $n$ 行，每行包含 $m$ 个字符，描述岛上当前的鳄鱼分布情况。

• 若格子为空，则用符号 . 表示；
• 若格子中有一只鳄鱼，则用一个字母表示它的逃跑方向：
• N —— 向北；
• S —— 向南；
• E —— 向东；
• W —— 向西。

输出格式

输出一个整数 —— 鲁滨逊最多能赶走而不激怒的鳄鱼数量。

1 5
WN.SE

4

1 3
E.W

0

3 4
.N.W
WWSS
EWEW

4

提示

样例解释

下图展示了第三个样例的情况：

:::align{center} :::

数据范围

本题包含三个子任务，每个子任务对应一组测试数据。只有当该子任务的所有测试数据均通过时，才能获得对应分值。

子任务编号	分值	限制条件
1	30	$1 \le n, m \le 30$
2		$1 \le n, m \le 500$
3	40	$1 \le n, m \le 2000$