Stone Game on a Grid

The stone game is played on a grid with n rows and m columns. Each cell on the grid is associated with an operation sequence. There are at most 10 distinct sequences, identified by the digits 0 through 9.

An operation sequence is a cyclic string of at most 6 characters. Every second, all cells execute the next character in their corresponding sequence (cycling back to the beginning if necessary). The operations are performed simultaneously for all cells based on the state from the previous second.

Each character in a sequence is one of the following, where any occurrence of a digit in {0,1,...,9} is interpreted as the following operation:

• Digit (0-9): Add that many stones to the cell. (The cell retains any stones it already had.)
• N, S, E, W: Push all stones from the cell to the adjacent cell in the corresponding direction (North, South, East, West respectively). If the adjacent cell does not exist (i.e. the cell is on the boundary), the stones are lost.
• D: Delete (remove) all stones from the cell.

The game starts with all cells empty. After t seconds the simulation finishes. Your task is to determine the maximum number of stones present in any cell after the simulation.

Note that if a cell executes a push operation, it transfers its entire stone count to the adjacent cell, and its own count becomes 0. Addition operations add the specified number of stones to the cell in addition to any stones already present, and the delete operation always clears the cell.

In mathematical terms, if we denote the stone count of a cell at time s as \(a_{i,j}(s)\) and let the operation performed be \(o_{i,j}(s)\), then the update rule is:

• If \(o_{i,j}(s)\) is a digit \(d\):
  \(a_{i,j}(s+1) = a_{i,j}(s) + d\)
• If \(o_{i,j}(s) = D\):
  \(a_{i,j}(s+1) = 0\)
• If \(o_{i,j}(s)\) is one of \(N, S, E, W\):
  the cell at \((i,j)\) transfers all its stones to the adjacent cell in that direction (if exists), and its stone count becomes 0.

All operations in a second are applied simultaneously.

inputFormat

The input is given as follows:

n m t
S0
S1
S2
S3
S4
S5
S6
S7
S8
S9
R1
R2
...
Rn

where:

• n, m and t are integers representing the number of rows, columns, and seconds of simulation respectively.
• The next 10 lines each contain a string (of length at most 6) representing the operation sequence corresponding to digit 0 through 9. For example, the first line is the sequence for cells marked with '0', the second line is for '1', and so on.
• Then follow n lines, each containing a string of m characters. Each character is a digit between 0 and 9, indicating which operation sequence the cell uses.

outputFormat

Output a single integer representing the maximum number of stones present in any cell after the simulation of t seconds.

sample

1 1 5
1
D
S
E
W
N
12
21
3
0
0

5