Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3402
Marble

Time Limit: 10 Seconds      Memory Limit: 65536 KB

The board of marble game can be represented by a two-dimention array which has n rows and m columns. There are act different operation sequences in total. Each grid is assigned a number from 0 to act - 1, corresponding to different operation sequences.

The length of operation sequence is no more than 6. And all of the sequence are executed repeatedly. For example, if the sequence is "1ED1D", it represents "1ED1D1ED1D1ED1D..." in fact. The sequence includes three types of operations:

  • Digit i (0 ≤ i ≤ 9) : add i marbles to the corresponding grid;
  • Letter 'N', 'W', 'S' or 'E': move all marbles in the grid to the corresponding adjacent grid ('N' means north, 'W' means west, 'S' means south, 'E' means east);
  • Letter 'D': empty the corresponding grid.
What's the maximum number of marbles among all grids, at t-th second?

All sequences operate simultaneously while the first operation starts at 1 second. There are no marbles at 0-th second, and marbles moved outside of the board will disappear.

Input

There are multiple cases. For each test case, the first line contains four integers n, m, t, act. The following n lines, each line contains m digits, indicate the corresponding operation sequence of the grid. Last act lines, each line contains a string of characters, indicate the details of every operation sequence. 1 ≤ n, m ≤ 15, 1 ≤ act ≤ 10, 1 ≤ t ≤ 109.

Output

For each case, output one integer number in a single line.

Sample Input

1 6 10 3
011112
1E
E
0

Sample Output

3

Hint

The sample input functions as a conveyor belt. On the left, the device of type 0 alternately grabs one marble and pushes it east. The devices of type 1 move the marble along to the east until they reach the device of type 2, which accumulates the marbles. After 10 cycles, 5 marbles have been brought up. 2 are still on the "conveyor belt", and 3 are on the square at the east end.


Author: HE, Ningxu
Contest: ZOJ Monthly, September 2010
Submit    Status