Czy znasz firmę Just Odd Inventions Co., Ltd.? Zajmuje się ona „po prostu dziwnymi wynalazkami”. Tutaj będziemy ją nazywać firmą JOI.

Firma JOI opracowała nowego wirusa „JOI Virus”. Chce przeprowadzić eksperyment, zakażając nim mieszkańców wyspy IOI.

Wyspa IOI ma kształt prostokąta. Biegnie przez nią $R-1$ równoległych dróg ze wschodu na zachód oraz $C-1$ równoległych dróg z północy na południe. Dzielą one wyspę na $RC$ obszarów. W każdym obszarze mieszka dokładnie jeden mieszkaniec. Mieszkańca obszaru $i$-tego od północy i $j$-tego od zachodu ($1 \le i \le R$, $1 \le j \le C$) nazywamy „mieszkańcem $(i,j)$”.

Na wyspie IOI każda doba składa się z $M$ okresów. Okres $k$ nazywamy „okresem $k$”. Wiatr zawsze wieje z jednego z kierunków: północy, południa, wschodu lub zachodu. Kierunek może zależeć od okresu. W tym samym okresie wiatr wieje z tego samego kierunku niezależnie od dnia.

Każdy mieszkaniec ma cechę „odporność”. Odporność mieszkańca $(i,j)$ ($1 \le i \le R$, $1 \le j \le C$) jest opisana nieujemną liczbą całkowitą $U_{i,j}$.

• Jeśli $U_{i,j}=0$, mieszkaniec $(i,j)$ ma wysoką odporność i nie zakaża się wirusem JOI Virus.

• Jeśli $U_{i,j}$ jest dodatnią liczbą całkowitą, mieszkaniec $(i,j)$ może się zakazić wirusem JOI Virus. Jeśli poniższy warunek zachodzi nieprzerwanie przez $U_{i,j}$ okresów, zostanie zakażony od następnego okresu:

  • Mieszkaniec sąsiedniego obszaru po stronie, z której wieje wiatr, jest już zakażony wirusem JOI Virus.

Zauważ, że ostatni okres danej doby i pierwszy okres następnej doby są kolejne.

Ze względu na cel eksperymentu chcemy zakazić co najmniej jednego mieszkańca, ale nie chcemy zakazić ich zbyt wielu. Na początku wybieramy jednego mieszkańca jako pierwszą zakażoną osobę i zakażamy go wirusem JOI Virus. Nie możemy wybrać mieszkańca o odporności równej $0$ jako pierwszej zakażonej osoby.

Mając dane kierunki, z których wieje wiatr w poszczególnych okresach, oraz odporność każdego mieszkańca, napisz program obliczający minimalną liczbę zakażonych mieszkańców po $10^{100}$ dniach oraz liczbę mieszkańców, których wybranie jako pierwszej zakażonej osoby prowadzi do tego minimum.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

$$ \begin{array}{lll} M & R & C \\ D \\ U_{1,1} & \cdots & U_{1,C} \\ \vdots & & \vdots \\ U_{R,1} & \cdots & U_{R,C} \end{array} $$

$D$ jest napisem długości $M$ opisującym kierunki, z których wieje wiatr na wyspie IOI. $D$ zawiera cztery rodzaje znaków: N, S, W lub E. Znak $k$-ty ($1 \le k \le M$) oznacza kierunek, z którego wieje wiatr w okresie $k$. Zauważ, że nie jest to kierunek, w którym wieje wiatr. N oznacza północ, S południe, W zachód, a E wschód.

Wyjście

Wypisz dwa wiersze na standardowe wyjście.

Pierwszy wiersz powinien zawierać minimalną liczbę zakażonych mieszkańców po $10^{100}$ dniach. Drugi wiersz powinien zawierać liczbę mieszkańców, których wybranie jako pierwszej zakażonej osoby prowadzi do minimalnej liczby zakażonych mieszkańców.

Ograniczenia

• $1 \le M \le 100\,000$.
• $1 \le R \le 800$.
• $1 \le C \le 800$.
• $D$ jest napisem długości $M$, zawierającym wyłącznie N, S, W i E.
• $0 \le U_{i,j} \le 100\,000$ ($1 \le i \le R$, $1 \le j \le C$).
• Istnieje co najmniej jedna para $(i,j)$ taka, że $1 \le U_{i,j}$ ($1 \le i \le R$, $1 \le j \le C$).

Podzadania

1. (14 punktów) $D$ zawiera wyłącznie W i E.
2. (6 punktów) $1 \le R \le 50$, $1 \le C \le 50$.
3. (80 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2

Wyjście 1

8
8

Uwagi

Rozważmy wybór mieszkańca $(3,1)$ jako pierwszej zakażonej osoby.

• Dla mieszkańca $(2,1)$ w okresie $1$ dnia $1$ wiatr wieje z południa, a sąsiad z południa jest już zakażony. Mieszkaniec ten zostanie więc zakażony od okresu $2$ dnia $1$.
• Dla mieszkańca $(3,2)$ w okresie $2$ dnia $1$ wiatr wieje z zachodu, a sąsiad z zachodu jest już zakażony. Mieszkaniec ten zostanie więc zakażony od okresu $3$ dnia $1$.
• Dla mieszkańca $(1,1)$ w okresie $6$ dnia $1$ wiatr wieje z południa, a sąsiad z południa jest już zakażony. Również w okresie $1$ dnia $2$ wiatr wieje z południa, a sąsiad z południa jest już zakażony. Mieszkaniec ten zostanie więc zakażony od okresu $2$ dnia $2$.
• Dla mieszkańca $(1,2)$ w okresie $2$ dnia $2$ wiatr wieje z zachodu, a sąsiad z zachodu jest już zakażony. Mieszkaniec ten zostanie więc zakażony od okresu $3$ dnia $2$.
• Dla mieszkańca $(1,3)$ w okresie $2$ dnia $3$ wiatr wieje z zachodu, a sąsiad z zachodu jest już zakażony. Mieszkaniec ten zostanie więc zakażony od okresu $3$ dnia $3$.
• Dla mieszkańca $(2,3)$ w okresie $3$ dnia $3$ wiatr wieje z północy, a sąsiad z północy jest już zakażony. Mieszkaniec ten zostanie więc zakażony od okresu $4$ dnia $3$.
• Dla mieszkańca $(3,3)$ w okresie $2$ dnia $4$ wiatr wieje z zachodu, a sąsiad z zachodu jest już zakażony. Następnie w okresie $3$ dnia $4$ wiatr wieje z północy, a sąsiad z północy jest już zakażony. Mieszkaniec ten zostanie więc zakażony od okresu $4$ dnia $4$.

Żaden kolejny mieszkaniec nie zostanie zakażony wirusem JOI Virus. Zatem jeśli wybierzemy mieszkańca $(3,1)$ jako pierwszą zakażoną osobę, po $10^{100}$ dniach zakażonych będzie $8$ mieszkańców.

Niezależnie od tego, którego mieszkańca wybierzemy jako pierwszą zakażoną osobę, nie możemy sprawić, by po $10^{100}$ dniach zakażonych wirusem JOI Virus było mniej niż $8$ mieszkańców, więc w pierwszym wierszu należy wypisać $8$. Jeśli jako pierwszą zakażoną osobę wybierzemy mieszkańca $(1,1)$, $(1,2)$, $(1,3)$, $(2,1)$, $(2,3)$, $(3,1)$, $(3,2)$ lub $(3,3)$, liczba zakażonych po $10^{100}$ dniach wyniesie $8$, więc w drugim wierszu należy wypisać $8$.

Wejście 2

4 4 4
EWWE
1 2 1 2
1 1 1 1
0 0 0 0
2 2 2 4

Wyjście 2

3
3

Uwagi

Ten przykład wejścia i wyjścia spełnia ograniczenia podzadania 1.