题目描述

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

操作序列是一个不超过 $6$ 且循环执行，每一秒执行一个字符的字符串。每秒钟所有格子同时执行各自操作序列里的下一个字符，序列的字符是以下格式之一：

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

输入格式

第一行三个整数 $n,m,t,{\rm act}$ 。 接下来 $n$ 行，每行 $m$ 个字符，表示每个格子对应的操作序列。 最后 ${\rm act}$ 行，每行一个字符串，表示从 $0$ 开始的每个操作序列。

输出格式

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

1 6 10 3
011112
1E
E
0

3

提示

【样例解释】

这是另一个类似于传送带的结构。左边的设备 $0$ 间隔地产生石头并向东传送。设备 $1$ 向右传送，直到设备 $2$。$10$ 秒后，总共产生了 $5$ 个石头，$2$ 个在传送带上，$3$ 个在最右边。

【数据约定】

$0\le n,m\le 8$,$1\le{\rm act}\le 10$,$1\le t\le 10^9$

题目来源

没有写明来源