题目描述

石头游戏在一个 $n$ 行 $m$ 列的网格上进行，每个格子对应一种操作序列，操作序列至多有 $10$ 种，分别用 $0 \sim 9$ 这 $10$ 个数字指明。

操作序列是一个长度不超过 $6$ 且循环执行、每秒执行一个字符的字符串。

每秒钟，所有格子同时执行各自操作序列里的下一个字符。

序列中的每个字符是以下格式之一：

• 数字 $0 \sim 9$：表示拿 $0 \sim 9$ 个石头到该格子。
• NWSE：表示把这个格子内所有的石头推到相邻的格子，N 表示上方，W 表示左方，S 表示下方，E 表示右方。
• D：表示拿走这个格子的所有石头。

给定每种操作序列对应的字符串，以及网格中每个格子对应的操作序列，求石头游戏进行了 $t$ 秒之后，石头最多的格子里有多少个石头。

在游戏开始时，网格是空的。

输入格式

第一行 $4$ 个整数 $n,m,t,act$。

接下来 $n$ 行，每行 $m$ 个字符，表示每个格子对应的操作序列编号（字符为 $0$ 到 $9$ 的数字）。

最后 $act$ 行，每行一个字符串，表示从 $0$ 开始的每个操作序列的具体内容。

输出格式

一个整数：游戏进行了 $t$ 秒之后，所有方格中石头最多的格子有多少个石头。

样例

输入样例：

1 6 10 3
011112
1E
E
0

输出样例：

3

样例解释

$n=1, m=6, t=10, act=3$

网格中每个格子的操作序列编号：

• 格子1: 0 → 操作序列内容为 1E
• 格子2: 1 → 操作序列内容为 E
• 格子3: 1 → E
• 格子4: 1 → E
• 格子5: 1 → E
• 格子6: 2 → 操作序列内容为 0

操作序列内容：

• 0: 1E
• 1: E
• 2: 0

模拟10秒后，石头最多的格子有 $3$ 个石头。

数据范围

• $1 \le n,m \le 8$
• $1 \le t \le 10^8$
• $1 \le act \le 10$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB