Kennst du Just Odd Inventions Co., Ltd.? Dieses Unternehmen beschäftigt sich mit „einfach seltsamen Erfindungen“. Hier nennen wir es kurz JOI Company.

JOI Company hat ein neues Virus namens „JOI Virus“ entwickelt. JOI Company möchte ein Experiment durchführen, indem es die Einwohner von IOI Island mit JOI Virus infiziert.

IOI Island hat die Form eines Rechtecks. Es gibt $R-1$ parallele Straßen von Ost nach West und $C-1$ parallele Straßen von Nord nach Süd. Sie teilen die Insel in $RC$ Gebiete. In jedem Gebiet wohnt genau ein Einwohner. Den Einwohner im $i$-ten Gebiet von Norden und $j$-ten Gebiet von Westen ($1 \le i \le R$, $1 \le j \le C$) nennen wir „Einwohner $(i,j)$“.

Auf IOI Island besteht ein Tag aus $M$ Zeitabschnitten. Den $k$-ten Zeitabschnitt nennen wir „Zeitabschnitt $k$“. Es weht immer Wind aus einer der vier Richtungen Norden, Süden, Osten oder Westen. Die Richtung kann sich je nach Zeitabschnitt ändern. Im selben Zeitabschnitt weht der Wind unabhängig vom Tag stets aus derselben Richtung.

Jeder Einwohner besitzt eine Eigenschaft namens „Resistenz“. Die Resistenz von Einwohner $(i,j)$ ($1 \le i \le R$, $1 \le j \le C$) wird durch eine nichtnegative ganze Zahl $U_{i,j}$ dargestellt.

• Ist $U_{i,j}=0$, bedeutet dies, dass Einwohner $(i,j)$ eine hohe Resistenz besitzt und sich nicht mit JOI Virus infiziert.

• Ist $U_{i,j}$ eine positive ganze Zahl, kann sich Einwohner $(i,j)$ mit JOI Virus infizieren. Wenn die folgende Bedingung während $U_{i,j}$ aufeinanderfolgender Zeitabschnitte erfüllt ist, ist dieser Einwohner ab dem nächsten Zeitabschnitt infiziert:

  • Der Einwohner im angrenzenden Gebiet in der Richtung, aus der der Wind kommt, ist bereits mit JOI Virus infiziert.

Beachte, dass der letzte Zeitabschnitt eines Tages und der erste Zeitabschnitt des nächsten Tages unmittelbar aufeinanderfolgen.

Für das Experiment möchten wir mindestens einen Einwohner infizieren, aber nicht zu viele. Zu Beginn wählen wir einen Einwohner als erste infizierte Person aus und infizieren diese Person mit JOI Virus. Ein Einwohner mit Resistenz $0$ darf nicht als erste infizierte Person ausgewählt werden.

Gegeben sind die Richtung, aus der der Wind in jedem Zeitabschnitt kommt, und die Resistenz jedes Einwohners. Schreibe ein Programm, das die minimale Anzahl infizierter Einwohner nach $10^{100}$ Tagen sowie die Anzahl der Einwohner berechnet, deren Auswahl als erste infizierte Person dieses Minimum erreicht.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

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

$D$ ist eine Zeichenkette der Länge $M$, die die Richtungen angibt, aus denen der Wind auf IOI Island kommt. $D$ besteht aus den vier möglichen Zeichen N, S, W und E. Das $k$-te Zeichen ($1 \le k \le M$) bezeichnet die Richtung, aus der der Wind im Zeitabschnitt $k$ kommt. Beachte, dass dies nicht die Richtung ist, in die der Wind weht. N steht für Norden, S für Süden, W für Westen und E für Osten.

Ausgabe

Schreibe zwei Zeilen auf die Standardausgabe.

Die erste Zeile soll die minimale Anzahl infizierter Einwohner nach $10^{100}$ Tagen enthalten. Die zweite Zeile soll die Anzahl der Einwohner enthalten, deren Auswahl als erste infizierte Person diese minimale Anzahl infizierter Einwohner erreicht.

Beschränkungen

• $1 \le M \le 100\,000$.
• $1 \le R \le 800$.
• $1 \le C \le 800$.
• $D$ ist eine Zeichenkette der Länge $M$, die nur N, S, W und E enthält.
• $0 \le U_{i,j} \le 100\,000$ ($1 \le i \le R$, $1 \le j \le C$).
• Es gibt mindestens ein Paar $(i,j)$ mit $1 \le U_{i,j}$ ($1 \le i \le R$, $1 \le j \le C$).

Teilaufgaben

1. (14 Punkte) $D$ enthält nur W und E.
2. (6 Punkte) $1 \le R \le 50$, $1 \le C \le 50$.
3. (80 Punkte) Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

8
8

Hinweis

Betrachten wir den Fall, dass Einwohner $(3,1)$ als erste infizierte Person ausgewählt wird.

• Für Einwohner $(2,1)$ weht der Wind im Zeitabschnitt $1$ des Tages $1$ aus Süden, und der benachbarte Einwohner im Süden ist bereits infiziert. Daher ist Einwohner $(2,1)$ ab Zeitabschnitt $2$ des Tages $1$ infiziert.
• Für Einwohner $(3,2)$ weht der Wind im Zeitabschnitt $2$ des Tages $1$ aus Westen, und der benachbarte Einwohner im Westen ist bereits infiziert. Daher ist Einwohner $(3,2)$ ab Zeitabschnitt $3$ des Tages $1$ infiziert.
• Für Einwohner $(1,1)$ weht der Wind im Zeitabschnitt $6$ des Tages $1$ aus Süden, und der benachbarte Einwohner im Süden ist bereits infiziert. Im Zeitabschnitt $1$ des Tages $2$ weht der Wind ebenfalls aus Süden, und der benachbarte Einwohner im Süden ist bereits infiziert. Daher ist Einwohner $(1,1)$ ab Zeitabschnitt $2$ des Tages $2$ infiziert.
• Für Einwohner $(1,2)$ weht der Wind im Zeitabschnitt $2$ des Tages $2$ aus Westen, und der benachbarte Einwohner im Westen ist bereits infiziert. Daher ist Einwohner $(1,2)$ ab Zeitabschnitt $3$ des Tages $2$ infiziert.
• Für Einwohner $(1,3)$ weht der Wind im Zeitabschnitt $2$ des Tages $3$ aus Westen, und der benachbarte Einwohner im Westen ist bereits infiziert. Daher ist Einwohner $(1,3)$ ab Zeitabschnitt $3$ des Tages $3$ infiziert.
• Für Einwohner $(2,3)$ weht der Wind im Zeitabschnitt $3$ des Tages $3$ aus Norden, und der benachbarte Einwohner im Norden ist bereits infiziert. Daher ist Einwohner $(2,3)$ ab Zeitabschnitt $4$ des Tages $3$ infiziert.
• Für Einwohner $(3,3)$ weht der Wind im Zeitabschnitt $2$ des Tages $4$ aus Westen, und der benachbarte Einwohner im Westen ist bereits infiziert. Im Zeitabschnitt $3$ des Tages $4$ weht der Wind aus Norden, und der benachbarte Einwohner im Norden ist bereits infiziert. Daher ist Einwohner $(3,3)$ ab Zeitabschnitt $4$ des Tages $4$ infiziert.

Kein weiterer Einwohner infiziert sich mit JOI Virus. Wenn Einwohner $(3,1)$ als erste infizierte Person ausgewählt wird, sind daher nach $10^{100}$ Tagen $8$ Einwohner mit JOI Virus infiziert.

Unabhängig davon, welcher Einwohner als erste infizierte Person ausgewählt wird, kann die Anzahl der nach $10^{100}$ Tagen mit JOI Virus infizierten Einwohner nicht kleiner als $8$ werden. Daher soll die erste Zeile $8$ enthalten. Wird einer der Einwohner $(1,1),(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)$ oder $(3,3)$ als erste infizierte Person ausgewählt, sind nach $10^{100}$ Tagen $8$ Einwohner infiziert. Daher soll die zweite Zeile $8$ enthalten.

Eingabe 2

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

Ausgabe 2

3
3

Hinweis

Diese Beispieleingabe und -ausgabe erfüllt die Beschränkungen von Teilaufgabe 1.