바이러스 실험

Just Odd Inventions Co., Ltd.를 아시나요? 이 회사의 사업은 '쓸모없어 보이는 기묘한 발명'이며, 이하에서는 JOI 회사라고 부르겠습니다.

JOI 회사는 새 바이러스 'JOI 바이러스'를 개발했습니다. 회사는 IOI 섬 주민들을 이 바이러스에 감염시키는 실험을 하려고 합니다.

IOI 섬은 직사각형 모양입니다. 동서 방향으로 나란한 도로가 $R-1$개, 남북 방향으로 나란한 도로가 $C-1$개 있어서 섬을 $RC$개의 구역으로 나눕니다. 각 구역에는 주민이 한 명씩 살고 있습니다. 북쪽에서 $i$번째, 서쪽에서 $j$번째 구역에 사는 주민을 주민 $(i, j)$라고 부릅니다. 여기서 $1 \le i \le R$, $1 \le j \le C$입니다.

하루는 $M$개의 시간대로 나뉩니다. $k$번째 시간대를 시간대 $k$라고 부릅니다. 바람은 북, 남, 동, 서 중 한 방향에서 항상 붑니다. 바람이 부는 방향은 시간대마다 바뀔 수 있지만, 같은 시간대에는 며칠이든 같은 방향에서 붑니다.

각 주민에게는 저항력 $U_{i,j}$가 있으며, 이는 음이 아닌 정수입니다.

• $U_{i,j}=0$이면 주민 $(i,j)$는 저항력이 높아서 감염되지 않습니다.
• $U_{i,j}$가 양의 정수이면 주민 $(i,j)$는 감염될 수 있습니다. 바람이 불어오는 방향의 인접 구역 주민이 감염된 상태가 $U_{i,j}$개의 시간대 동안 계속 유지되면, 그다음 시간대부터 주민 $(i,j)$가 감염됩니다.

하루의 마지막 시간대와 다음 날의 첫 시간대는 이어진다고 봅니다.

실험에서는 최소 한 명은 감염시키되, 너무 많이 감염시키지 않는 것이 목적입니다. 처음에 감염자 한 명을 고르고, 그 사람에게 바이러스를 주입합니다. 저항력이 0인 주민은 처음 감염자로 고를 수 없습니다.

시간대별 바람 방향과 각 주민의 저항력이 주어졌을 때, $10^{100}$일 후 감염자 수의 최솟값을 구하세요. 또한 그 최솟값을 만드는 처음 감염자의 수도 구하세요.

첫째 줄에 $M$, $R$, $C$가 주어집니다. 둘째 줄에는 길이가 $M$인 문자열 $D$가 주어집니다. $D$의 $k$번째 문자는 시간대 $k$에 바람이 불어오는 방향입니다. 바람이 불어가는 방향이 아니라 불어오는 방향이라는 점에 유의하세요. N은 북, S는 남, W는 서, E는 동을 뜻합니다.

이후 $R$개의 줄에 각각 $C$개의 정수가 주어집니다. $i$번째 줄의 $j$번째 정수가 $U_{i,j}$입니다.

두 줄을 출력합니다. 첫째 줄에는 $10^{100}$일 후 감염자 수의 최솟값을 출력합니다. 둘째 줄에는 그 최솟값을 달성하는 처음 감염자의 수를 출력합니다.

• $1 \le M \le 100\,000$
• $1 \le R \le 800$
• $1 \le C \le 800$
• $D$의 길이는 $M$이며, N, S, W, E 문자만 포함합니다.
• $1 \le i \le R$, $1 \le j \le C$에 대해 $0 \le U_{i,j} \le 100\,000$입니다.
• $1 \le U_{i,j}$를 만족하는 $(i, j)$가 적어도 하나 있습니다.