石头游戏

内存限制：256 MiB 时间限制：10 Sec

石头游戏的规则是这样的。

石头游戏在一个n行m列的方格阵上进行。每个格子对应了一个编号在0~9之间的操作序列。

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

数字0~9：拿0~9个石头到该格子。

NWSE：把这个格子内所有的石头推到相邻的格子。

D：拿走这个格子的石头。

石头游戏的问题是：当这个石头游戏进行了t秒之后，所有方格中最多的格子有多少个石头。

注意：所有格子的操作同时执行。

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

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

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

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


			3

【样例解释】

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

【数据约定】

0≤n, m≤8。

1≤act≤10。

1≤t≤10^9。

#2973. 石头游戏