Problem Description

The stone game is played on a grid with $n$ rows and $m$ columns. Each cell corresponds to an operation sequence. There are at most $10$ kinds of operation sequences, denoted by the digits $0 \sim 9$.

An operation sequence is a string of length at most $6$ that repeats in a cycle, executing one character per second.

Every second, all cells execute the next character in their own operation sequence at the same time.

Each character in a sequence is one of the following:

1. A digit $0 \sim 9$: move $0 \sim 9$ stones into this cell.
2. NWSE: push all stones in this cell to an adjacent cell. N means up, W means left, S means down, and E means right. If the operation is invalid (i.e., the stones would be pushed out of the grid), then the stones disappear.
3. D: remove all stones from this cell.

You are given the string for each operation sequence, and for each cell in the grid, which operation sequence it uses. Find, after $t$ seconds, how many stones are in the cell that has the most stones.

At the start of the game, the grid is empty.

Input Format

The first line contains $4$ integers $n, m, t, act$.

The next $n$ lines each contain $m$ characters, indicating the operation sequence used by each cell.

The last $act$ lines each contain one string, describing each operation sequence starting from $0$.

Output Format

Output one integer: after $t$ seconds, the maximum number of stones among all cells.

1 6 10 3
011112
1E
E
0

3

Hint

For all testdata, $1 \le m, n \le 8$, $1 \le t \le 10^8$, $1 \le act \le 10$.

Translated by ChatGPT 5