题目描述

译自 JOI Open 2019 T3「ウイルス実験 / Virus Experiment」

你知道「净是一些鬼畜发明公司」（Just Odd Inventions Co., Ltd.）吗？这家公司就是发明一些鬼畜玩意的。现在我们就叫它 JOI 公司。

JOI 公司开发了一种新型病毒——「JOI 病毒」。JOI 公司想要通过用 JOI 病毒感染 IOI 岛上的居民的方式做一次病毒实验。

IOI 岛是一个矩形，从东向西有 $R-1$ 条互相平行的街道，从北向南有 $C-1$ 条互相平行的街道。它们把岛划分为 $RC$ 个区域。每个区域只住着一个居民，我们称住在从北数第 $i$ 区域，从西数第 $j$ 个区域的居民为居民 $(i,j)$。

在 IOI 岛上，一天共有 $M$ 个时间段。我们称第 $k$ 个时间段为时段 $k$。风总是从东西南北四个方向吹来，风向取决于时段。如果时段相同，则风向相同，与日期无关。

每个居民都有一个抵抗力。居民 $(i,j)$ 的抵抗力用一个非负整数 $U_{i,j}$ 表示。

• 如果 $U_{i,j}=0$，表示居民 $(i,j)$ 的抵抗力很高，并且这位居民不会感染 JOI 病毒；
• 如果 $U_{i,j}>0$，表示居民 $(i,j)$ 可能会感染 JOI 病毒。如果以下情况持续了 $U_{i,j}$ 个时段，这位居民就将在下一个时段感染 JOI 病毒：
  • 住在风吹来方向且与这位居民相邻的居民感染了 JOI 病毒。

注意一天最后一个时段和下一天第一个时段是连续的。

为了完成实验，我们想要至少感染一位居民，但是我们不想感染太多的居民。在初始的时候，我们选择一位居民作为第一个被感染的人，然后使他感染 JOI 病毒。我们不能感染抵抗力为 0 的居民。

给定每一个时段的风向，写一个程序计算在 $10^{100}$ 天之后至少会有多少居民被感染，和达到这个最小值选择初始感染者的方案数。

输入格式

第一行三个正整数 $M,R,C$，意义如题目描述。

接下来一行一个长为 $M$ 的字符串 $D$，表示一天中每个时段的风向。$D$ 中只包含 N，S，W，E 四种字符。第 $k\ (1\le k\le M)$ 个字符表示时段 $k$ 风的来向，N 代表风从北吹来，S 表示风从南方吹来，W 表示风从西吹来，E 表示风从东吹来。

接下来 $R$ 行，每行 $C$ 个整数。第 $i$ 行第 $j$ 列的整数 $U_{i,j}$ 表示居民 $(i,j)$ 的抵抗力。

输出格式

输出两行。第一行表示在 $10^{100}$ 天之后至少能感染居民的数量。第二行输出达到这个最小值的情况下选择初始感染者的方案数。

样例

样例 1

输入

6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2

输出

8
8

样例说明

考虑当居民 $(3,1)$ 是初始感染者的情况。

• 对于居民 $(2,1)$，在第 1 天的时段 1，风从南方吹来，并且位于他南方的相邻居民（即居民 $(3,1)$）已经感染了病毒，因此这位居民将在第 1 天的时段 2 感染；
• 对于居民 $(3,2)$，在第 1 天的时段 2，风从西方吹来，并且位于他西方的相邻居民（即居民 $(3,1)$）已经感染了病毒，因此这位居民将在第 1 天的时段 3 感染；
• 对于居民 $(1,1)$，在第 1 天的时段 6，风从南方吹来，并且位于他南方的相邻居民（即居民 $(2,1)$）已经感染了病毒，在第 2 天的时段 1，风从南方吹来，并且位于他南方的相邻居民（即居民 $(2,1)$）已经感染了病毒，因此这位居民将在第 2 天的时段 2 感染；
• 对于居民 $(1,2)$，在第 2 天的时段 2，风从西方吹来，并且位于他西方的相邻居民（即居民 $(1,1)$）已经感染了病毒，因此这位居民将在第 2 天的时段 3 感染；
• 对于居民 $(1,3)$，在第 3 天的时段 2，风从西方吹来，并且位于他西方的相邻居民（即居民 $(1,2)$）已经感染了病毒，因此这位居民将在第 3 天的时段 3 感染；
• 对于居民 $(2,3)$，在第 3 天的时段 3，风从北方吹来，并且位于他北方的相邻居民（即居民 $(1,3)$）已经感染了病毒，因此这位居民将在第 3 天的时段 4 感染；
• 对于居民 $(3,3)$，在第 4 天的时段 2，风从西方吹来，并且位于他西方的相邻居民（即居民 $(3,2)$）已经感染了病毒，在第 4 天的时段 3，风从北方吹来，并且位于他北方的相邻居民（即居民 $(2,3)$）已经感染了病毒，因此这位居民将在第 4 天的时段 4 感染。

这样就没有再多的居民会感染 JOI 病毒了。于是，当我们选择居民 $(3,1)$ 作为初始感染者的情况下，$10^{100}$ 天后就有 8 位居民被感染。

无论如何选择初始感染者，我们都不能让 $10^{100}$ 天后的病毒感染者人数小于 8，所以第一行输出 8。如果我们选择居民 $(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)$ 或者居民 $(3,3)$ 作为初始感染者，$10^{100}$ 天后感染者人数都为 8，因此第二行输出 8。

---

样例 2

输入

4 4 4
EWWE
1 2 1 2
1 1 1 1
0 0 0 0
2 2 2 4

输出

3
3

样例说明

这组样例满足子任务 1 的限制。

数据范围与提示

对于全部数据，$1\le M\le 10^5$，$1\le R,C\le 800$，$0\le U_{i,j}\le 10^5$，保证 $D$ 字符串长度为 $M$ 并且只包含 N，S，W，E 四种字符，并且保证至少有一个 $U_{i,j}\ge 1\ (1\le i\le R,1\le j\le C)$。

具体子任务附加限制及分值如下：

子任务	附加限制	分值
1	$D$ 中只包含 W 和 E 两种字符	14 分
2	$1\le R,C\le 50$	6 分
3	无附加限制	80 分