题目描述

石头游戏在一个 $\red n$ 行 $\red m$ 列 $\red{(1≤n,m≤8)}$ 的网格上进行，每个格子对应一种操作序列，操作序列至多有 $\red{10}$ 种，分别用$\red{0\sim9}$ 这 $\red{10}$ 个数字指明。

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

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

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

$\red 1$、数字 $\red{0\sim9}$ : 表示拿 $\red{0\sim9}$ 个石头到该格子。

$\red 2$、$\red{NWSE}$：表示把这个格子内所有的石头推到相邻的格子，$\red N$ 表示上方，$\red W$ 表示左方，$\red S$ 表示下方，$\red E$ 表示右方。

$\red 3$、$\red D$：表示拿走这个格子的所有石头。

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

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

输入格式

第一行 $\red 4$ 个整数 $\red n$, $\red m$, $\red t$, $\red{act}$。

接下来 $\red n$ 行，每行 $\red m$ 个字符，表示每个格子对应的操作序列。

最后 $\red{act}$ 行，每行一个字符串，表示从 $\red 0$ 开始的每个操作序列。

输出格式

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

样例

输入样例

1 6 10 3
011112
1E
E
0

输出样例

3

提示

$\red{1\leq m,n\leq8}$,

$\red{1\leq t\leq 10^8}$,

$\red{1\leq act\leq10}$

样例中给出了三组操作序列，第一个格子执行编号为$\red 0$的操作序列"$\red{1E}$”,第二至五个格子执行编号为 $\red 1$ 的操作序列"$\red E$”,第六个格子执行编号为 $\red 2$ 的操作序列"$\red 0$”。

这是另一个类似于传送带的结构，左边的设备 $\red 0$ 间隔地产生石头并向东传送。

设备 $\red 1$ 向右传送，直到设备 $\red 2$。

$\red{10}$ 秒后，总共产生了 $\red 5$ 个石头，$\red 2$ 个在传送带上，$\red 3$ 个在最右边。