Maximizing Piano Sliding Distance

The ballroom is represented as a matrix with \(N\) rows and \(M\) columns. Some cells contain furniture while others are empty. A piano can slide on an empty cell but will crash if it collides with furniture or slides out of the ballroom. At each time step, the ship tilts in a given direction (north, south, east, or west) and the piano will slide one cell in that direction unless Emily casts a magic spell. When she casts magic, the piano remains in its current cell. Emily knows the sequence of ship tilts ahead of time and wants the piano to slide through as many cells as possible without crashing.

Game rules:

• You are given a grid of size \(N \times M\). The grid cells are either empty (denoted by '0') or have furniture (denoted by '1').
• You are also given the starting position of the piano in the grid (1-indexed).
• The next \(T\) lines contain a sequence of tilts. Each tilt is represented by one of the characters N (north), S (south), E (east), or W (west).
• At each time step, you have two choices:
  • No Magic: The piano slides one cell in the given tilt direction. If the target cell is out-of-bounds or contains furniture, the move is not allowed (and would result in a crash).
  • Cast Magic: The piano stays in its current cell.
• The objective is to choose when to cast magic so as to maximize the total number of sliding moves (i.e. moves where the piano actually slides) during the \(T\) time steps.

Note: Use 1-indexed coordinates for the starting position in the input.

inputFormat

The first line contains three integers \(N\), \(M\), and \(T\) \( (1 \leq N, M \leq 100, 1 \leq T \leq 10^4)\) representing the number of rows, columns, and time steps respectively.

The next \(N\) lines each contain a string of length \(M\) consisting of characters '0' (empty cell) and '1' (furniture), representing the ballroom layout.

The following line contains two integers \(r\) and \(c\) \(1 \le r \le N, 1 \le c \le M\) representing the starting row and column of the piano.

The next \(T\) lines each contain a single character, one of 'N', 'S', 'E', or 'W', indicating the direction of the ship's tilt at that time step.

outputFormat

Output a single integer which is the maximum number of sliding moves the piano can make safely by optimally deciding when to cast magic.

sample

3 3 4
000
010
000
2 1
E
E
S
W

1