Connaissez-vous Just Odd Inventions Co., Ltd. ? L'activité de cette entreprise consiste à réaliser « des inventions tout simplement étranges ». Nous l'appellerons ici JOI Company.

JOI Company a développé un nouveau virus, « JOI Virus ». JOI Company souhaite mener une expérience en infectant les habitants de l'île IOI avec JOI Virus.

L'île IOI est rectangulaire. Elle comporte $R-1$ routes parallèles allant d'est en ouest et $C-1$ routes parallèles allant du nord au sud. Elles divisent l'île en $RC$ zones. Chaque zone abrite exactement un habitant. Nous appelons « habitant $(i,j)$ » celui qui vit dans la zone située au $i$-ème rang depuis le nord et au $j$-ème rang depuis l'ouest ($1 \le i \le R$, $1 \le j \le C$).

Sur l'île IOI, une journée comporte $M$ périodes. Nous appelons la $k$-ème période « période $k$ ». Le vent souffle toujours depuis l'une des quatre directions : nord, sud, est ou ouest. Sa direction peut changer selon la période. Pour une même période, le vent souffle depuis la même direction, quel que soit le jour.

Chaque habitant possède une caractéristique appelée « résistance ». La résistance de l'habitant $(i,j)$ ($1 \le i \le R$, $1 \le j \le C$) est représentée par un entier positif ou nul $U_{i,j}$.

• Si $U_{i,j}=0$, l'habitant $(i,j)$ a une résistance élevée et ne peut pas être infecté par JOI Virus.

• Si $U_{i,j}$ est strictement positif, l'habitant $(i,j)$ peut être infecté par JOI Virus. Si la condition suivante reste satisfaite pendant $U_{i,j}$ périodes consécutives, il sera infecté à partir de la période suivante :

  • L'habitant de la zone adjacente située dans la direction d'où vient le vent est déjà infecté par JOI Virus.

  Remarquez que la dernière période d'un jour et la première période du jour suivant sont consécutives.

Pour les besoins de l'expérience, nous voulons infecter au moins un habitant, mais pas trop. Au début, nous choisissons un habitant comme première personne infectée et lui transmettons JOI Virus. Nous ne pouvons pas choisir comme première personne infectée un habitant dont la résistance vaut $0$.

Étant données la direction d'où vient le vent à chaque période et la résistance de chaque habitant, écrivez un programme qui calcule le nombre minimal d'habitants infectés après $10^{100}$ jours, ainsi que le nombre d'habitants dont le choix comme première personne infectée permet d'atteindre ce minimum.

Entrée

Lisez les données suivantes sur l'entrée standard.

$$ \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$ est une chaîne de longueur $M$ décrivant la direction d'où vient le vent sur l'île IOI. Elle est composée des quatre caractères N, S, W et E. Le $k$-ème caractère ($1 \le k \le M$) indique la direction d'où vient le vent pendant la période $k$. Attention : il ne s'agit pas de la direction vers laquelle le vent souffle. N désigne le nord, S le sud, W l'ouest et E l'est.

Sortie

Écrivez deux lignes sur la sortie standard.

La première ligne doit contenir le nombre minimal d'habitants infectés après $10^{100}$ jours. La seconde doit contenir le nombre d'habitants dont le choix comme première personne infectée permet d'atteindre ce nombre minimal d'habitants infectés.

Contraintes

• $1 \le M \le 100\,000$.
• $1 \le R \le 800$.
• $1 \le C \le 800$.
• $D$ est une chaîne de longueur $M$ ne contenant que N, S, W et E.
• $0 \le U_{i,j} \le 100\,000$ ($1 \le i \le R$, $1 \le j \le C$).
• Il existe au moins une paire $(i,j)$ telle que $1 \le U_{i,j}$ ($1 \le i \le R$, $1 \le j \le C$).

Sous-tâches

1. (14 points) $D$ ne contient que W et E.
2. (6 points) $1 \le R \le 50$, $1 \le C \le 50$.
3. (80 points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

8
8

Remarque

Considérons le cas où nous choisissons l'habitant $(3,1)$ comme première personne infectée.

• Pour l'habitant $(2,1)$, pendant la période $1$ du jour $1$, le vent vient du sud et son voisin au sud est déjà infecté. Il sera donc infecté à partir de la période $2$ du jour $1$.
• Pour l'habitant $(3,2)$, pendant la période $2$ du jour $1$, le vent vient de l'ouest et son voisin à l'ouest est déjà infecté. Il sera donc infecté à partir de la période $3$ du jour $1$.
• Pour l'habitant $(1,1)$, pendant la période $6$ du jour $1$, le vent vient du sud et son voisin au sud est déjà infecté. Pendant la période $1$ du jour $2$, le vent vient également du sud et son voisin au sud est déjà infecté. Il sera donc infecté à partir de la période $2$ du jour $2$.
• Pour l'habitant $(1,2)$, pendant la période $2$ du jour $2$, le vent vient de l'ouest et son voisin à l'ouest est déjà infecté. Il sera donc infecté à partir de la période $3$ du jour $2$.
• Pour l'habitant $(1,3)$, pendant la période $2$ du jour $3$, le vent vient de l'ouest et son voisin à l'ouest est déjà infecté. Il sera donc infecté à partir de la période $3$ du jour $3$.
• Pour l'habitant $(2,3)$, pendant la période $3$ du jour $3$, le vent vient du nord et son voisin au nord est déjà infecté. Il sera donc infecté à partir de la période $4$ du jour $3$.
• Pour l'habitant $(3,3)$, pendant la période $2$ du jour $4$, le vent vient de l'ouest et son voisin à l'ouest est déjà infecté. Pendant la période $3$ du jour $4$, le vent vient du nord et son voisin au nord est déjà infecté. Il sera donc infecté à partir de la période $4$ du jour $4$.

Aucun autre habitant ne sera infecté par JOI Virus. Ainsi, si nous choisissons l'habitant $(3,1)$ comme première personne infectée, 8 habitants seront infectés par JOI Virus après $10^{100}$ jours.

Quel que soit l'habitant choisi comme première personne infectée, le nombre d'habitants infectés par JOI Virus après $10^{100}$ jours ne peut pas être inférieur à 8 ; il faut donc écrire 8 sur la première ligne. Si nous choisissons l'habitant $(1,1)$, $(1,2)$, $(1,3)$, $(2,1)$, $(2,3)$, $(3,1)$, $(3,2)$ ou $(3,3)$ comme première personne infectée, le nombre d'habitants infectés après $10^{100}$ jours sera de 8 ; il faut donc écrire 8 sur la seconde ligne.

Entrée 2

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

Sortie 2

3
3

Remarque

Cet exemple d'entrée et de sortie satisfait les contraintes de la sous-tâche 1.