题目描述

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

JOI 公司研究了新型病毒 JOI virus。JOI 公司希望通过用该病毒影响在 IOI 岛的动物做实验。

IOI 岛呈矩形。有 $R-1$ 条从西向东的平行道路，和 $C-1$ 条从北向南的平行道路。她们将岛分割成 $RC$ 个部分。每部分只有一只动物。我们称居住在北部第 $i$，西部第 $j$ 部分的动物为 动物(i,j)（$1\le i\le R$，$1\le j\le C$）。

在 IOI 岛上，一天有 $M$ 个时间段。我们管第 $k$ 个叫 时间段k。风总是从某方向吹来：北方，南方，东方和西方。基于时间段，风向可能改变。如果时间段相同，风向总是不变，这和在哪一天无关。

每只动物有一个状态 抵抗力。动物 $(i,j)$ 的抵抗力表示为一个非负整数 $U_{i,j}$。

• 如果 $U_{i,j}=0$,说明动物 $(i,j)$ 有很高的抵抗力，使得它不被 JOI virus 感染。

• 如果 $U_{i,j}$ 是一个正整数，说明动物 $(i,j)$ 可能被感染。如果下面条件连续成立了 $U_{i,j}$ 时间段，则他/她会从下一个时间段开始被感染。

  -- 从风向处相邻的动物已经被传染。

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

为了实验，我们希望至少感染 $1$ 只动物，但是我们不希望感染过多的动物。在开始，我们选择一只作为第一个被感染的。我们不能选择 $U_{i,j}=0$ 的动物 $(i,j)$ 作为第一个被感染的个体。

给定每个时间段的风向和每只动物的抵抗力。编写程序计算经过了 $10^{100}$ 天后最少被感染了个体数，和达成此目标刚开始能选择的个体有几种。

输入格式

第 $1$ 行三个整数 $M,R,C$。

第 $2$ 行一个整数 $D$。

第 $3\sim3+R-1$ 行，每行 $C$ 个整数。第 $i-3+1$ 行第 $j$ 列的数表示 $U_{i,j}$。

$D$ 是长 $M$ 的字符串表示风向。D 包含 $4$ 种字符：$\texttt N$, $\texttt S$, $\texttt W$, $\texttt E$。分别表示北南西东。第 $k$ 个字符（$1\le k\le M$）表示第 $k$ 个时间段的风向。

输出格式

第 $1$ 行一个数表示最少被感染个体数。

第 $2$ 行一个数表示使得被感染的个体最少，初始时有几种选法。

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

提示

样例解释：

让我们考虑选择动物 $(3,1)$ 作为初始被感染个体的情况。

对于动物 $(2,1)$，在第 $1$ 天的时间段 $1$，刮南风，且南边相邻动物已经被感染，所以他/她会从第 $1$ 天的时间段 $2$ 被感染。

对于动物 $(3,2)$，在第 $1$ 天的时间段 $2$，刮西风，且西边相邻动物已经被感染，所以他/她会从第 $1$ 天的时间段 $3$ 被感染。

对于动物 $(1,1)$，在第 $1$ 天的时间段 $6$，刮南风，且南边相邻动物已经被感染，且在第 $2$ 天的时间段 $1$，刮南风，且南边相邻动物已经被感染，所以他/她会从第 $2$ 天的时间段 $2$ 被感染。

对于动物 $(1,2)$，在第 $2$ 天的时间段 $2$，刮西风，且西边相邻动物已经被感染，所以他/她会从第 $2$ 天的时间段 $3$ 被感染。

对于动物 $(1,3)$，在第 $3$ 天的时间段 $2$，刮西风，且西边相邻动物已经被感染，所以他/她会从第 $3$ 天的时间段 $3$ 被感染。

对于动物 $(2,3)$，在第 $3$ 天的时间段 $3$，刮北风，且北边相邻动物已经被感染，所以他/她会从第 $3$ 天的时间段 $4$ 被感染。

对于动物 $(3,3)$，在第 $4$ 天的时间段 $2$，刮西风，且西边相邻动物已经被感染，且在第 $4$ 天的时间段 $3$，刮北风，且北边相邻动物已经被感染。所以他/她会从第 $4$ 天的时间段 $4$ 被感染。

没有更多动物会被感染。所以当选择 动物 $(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$。

这个样例满足 子任务1 的约束条件。

数据范围：

$1\le M\le 10^5$，$1\le R\le 800$，$1\le C\le 800$。

$D$ 是一个长度为 $M$ 的字符串，只包含 $\texttt N$, $\texttt S$, $\texttt W$, $\texttt E$。

$0\le U_{i,j}\le 10^5$（$1\le i\le R$，$1\le j\le C$）。

至少有一对 $(i,j)$ 满足 $1\le U_{i,j}$（$1\le i\le R$，$1\le j\le C$）。

子任务：

1. （14 分）$D$ 只包含 $\texttt W$ 和 $\texttt E$。
2. （6 分）$1\le W\le 50$，$1\le C\le 50$。
3. （80 分）无额外约束。