Welcome to ZOJ
96 - ZOJ Monthly, September 2010 - G

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.


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.


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

Sample Input

1 6 10 3

Sample Output



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