题目描述

译自 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}$ 天之后至少能感染居民的数量。第二行输出达到这个最小值的情况下选择初始感染者的方案数。

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

8
8

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

3
3

数据范围与提示

对于全部数据，$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$（$14$ 分）：$D$ 中只包含 W 和 E 两种字符；
• 子任务 $2$（$6$ 分）：$1\le R,C\le 50$；
• 子任务 $3$（$80$ 分）：无附加限制。