Virus Experiment

This problem is adapted from JOI Open 2019 T3 "ウイルス実験". In this experiment, a company studies the spread of a new virus called the JOI virus on IOI Island. The island is divided into a rectangular grid with R rows and C columns. Each grid cell contains an animal. The animal in the cell at the north‐i th row and west‐j th column is called animal(i,j) (1 ≤ i ≤ R, 1 ≤ j ≤ C).

There are M time segments in a day. For the k-th segment, we call it Time Segment k. In every time segment the wind blows from one of four directions: North, South, East, or West. Note that for the same time segment (regardless of the day) the wind direction is always the same.

Each animal has a non‐negative integer called its resistance. For animal (i,j) the resistance is denoted by U_i,j:

• If U_i,j = 0 then the animal is highly resistant and cannot be infected by the JOI virus.
• If U_i,j is a positive integer then the animal can be infected. However, if the following condition holds for U_i,j consecutive time segments then the animal becomes infected starting from the next time segment:
  In each of these consecutive segments, the animal adjacent in the direction from which the wind is blowing is already infected.

At the very start of the experiment, exactly one animal is chosen as the first infected individual. Note that an animal with U_i,j = 0 cannot be chosen initially.

Given the wind direction for each time segment and the resistance U_i,j for every animal in the grid, your task is to determine the minimum number of animals that will be infected after 10¹⁰⁰ days and the number of choices for the initial infected animal that achieve this minimum.

Note on the infection process: The infection condition is checked at each time segment. Suppose the wind direction in the current segment is d. Then, for a non‐infected animal in cell (i, j), let the candidate neighbor be the cell adjacent in the direction d. More precisely:

• If d is N (North) the candidate is (i-1, j).
• If d is S (South) the candidate is (i+1, j).
• If d is E (East) the candidate is (i, j+1).
• If d is W (West) the candidate is (i, j-1).

If this candidate exists and is infected at that moment then the animal (i,j) increases its consecutive exposure count by 1; otherwise, the count resets to 0. Once the count reaches U_i,j (for U_i,j > 0), the animal becomes infected from the next time segment onward. The process continues indefinitely (across days) until no new infections occur.

Your goal is to choose the initial infected animal (which must have U > 0) so that the final number of infected animals (after 10¹⁰⁰ days when the process stabilizes) is as small as possible. Output that minimal number and also the number of initial choices that produce this optimum outcome.

inputFormat

The input begins with a line containing three integers: R C M.

The next line contains M characters (each one of N, S, E, or W) separated by spaces representing the wind direction for each time segment.

Then follow R lines, each containing C integers. The j-th integer in the i-th line represents U_i,j (0 ≤ U_i,j ≤ 10⁹).

You may assume that R and C are small enough so that a simulation will finish in time.

outputFormat

Output two integers separated by a space: the minimum number of animals infected at the end and the number of initial choices (animals with U > 0) that yield this minimum.

sample

2 2 1
N
1 1
1 0

1 2