Virus Experiment

Do you know Just Odd Inventions Co., Ltd.? Its business is making 'just odd inventions,' and here we call it JOI Company.

JOI Company developed a new virus, the JOI Virus. The company wants to run an experiment by infecting the inhabitants of IOI Island with it.

IOI Island is rectangular. There are $R-1$ parallel roads running east to west and $C-1$ parallel roads running north to south. They divide the island into $RC$ sections, and each section has exactly one inhabitant. We call the inhabitant in the section that is the $i$-th from the north and the $j$-th from the west inhabitant $(i, j)$, where $1 \le i \le R$ and $1 \le j \le C$.

A day has $M$ time periods. We call the $k$-th time period time period $k$. Wind always blows from one of four directions: north, south, east, or west. The direction can change between time periods, but within the same time period, the wind blows from the same direction on every day.

Each inhabitant has a resistance value, a non-negative integer $U_{i,j}$.

• If $U_{i,j}=0$, inhabitant $(i,j)$ has high resistance and never gets infected.
• If $U_{i,j}$ is positive, inhabitant $(i,j)$ may get infected. If the neighbor in the direction the wind blows from stays infected for $U_{i,j}$ consecutive time periods, inhabitant $(i,j)$ becomes infected starting from the next time period.

The last time period of a day and the first time period of the next day are consecutive.

The experiment must infect at least one inhabitant, but the goal is to infect as few as possible. At the start, we choose one inhabitant as the first infected person and infect them. We cannot choose an inhabitant with resistance 0 as the first infected person.

Given the wind direction for each time period and the resistance of each inhabitant, compute the minimum number of infected inhabitants after $10^{100}$ days. Also compute how many choices of first infected inhabitant achieve that minimum.

The first line contains $M$, $R$, and $C$. The second line contains a string $D$ of length $M$. The $k$-th character of $D$ is the direction the wind blows from during time period $k$. Note that this is the direction the wind comes from, not the direction it blows toward. N means north, S means south, W means west, and E means east.

The next $R$ lines each contain $C$ integers. The $j$-th integer on the $i$-th line is $U_{i,j}$.

Print two lines. The first line contains the minimum number of infected inhabitants after $10^{100}$ days. The second line contains the number of inhabitants who reach that minimum when chosen as the first infected person.

• $1 \le M \le 100\,000$
• $1 \le R \le 800$
• $1 \le C \le 800$
• $D$ has length $M$ and contains only N, S, W, and E.
• $0 \le U_{i,j} \le 100\,000$ for $1 \le i \le R$ and $1 \le j \le C$.
• At least one pair $(i, j)$ satisfies $1 \le U_{i,j}$.