Apakah Anda mengenal Just Odd Inventions Co., Ltd.? Bisnis perusahaan ini adalah membuat “penemuan yang aneh saja”. Di sini kita menyebutnya JOI Company.

JOI Company mengembangkan virus baru, “JOI Virus”. JOI Company ingin melakukan eksperimen dengan menginfeksi penduduk IOI Island menggunakan JOI Virus.

IOI Island berbentuk persegi panjang. Terdapat $R-1$ jalan sejajar dari timur ke barat dan $C-1$ jalan sejajar dari utara ke selatan. Jalan-jalan ini membagi pulau menjadi $RC$ bagian. Setiap bagian dihuni oleh tepat 1 penduduk. Penduduk yang tinggal di bagian ke-$i$ dari utara dan ke-$j$ dari barat ($1 \le i \le R$, $1 \le j \le C$) disebut “penduduk $(i,j)$”.

Di IOI Island, satu hari terdiri dari $M$ periode waktu. Periode waktu ke-$k$ disebut “periode waktu $k$”. Angin selalu bertiup dari salah satu arah: utara, selatan, timur, atau barat. Arahnya dapat berubah menurut periode waktu. Pada periode waktu yang sama, angin bertiup dari arah yang sama, terlepas dari harinya.

Setiap penduduk memiliki suatu status yang disebut “ketahanan”. Ketahanan penduduk $(i,j)$ ($1 \le i \le R$, $1 \le j \le C$) dinyatakan dengan bilangan bulat nonnegatif $U_{i,j}$.

• Jika $U_{i,j}=0$, penduduk $(i,j)$ memiliki ketahanan tinggi dan tidak akan terinfeksi JOI Virus.

• Jika $U_{i,j}$ adalah bilangan bulat positif, penduduk $(i,j)$ dapat terinfeksi JOI Virus. Jika kondisi berikut berlangsung selama $U_{i,j}$ periode waktu berturut-turut, ia akan terinfeksi mulai periode waktu berikutnya:

  • Penduduk yang tinggal di bagian yang bersebelahan pada arah asal angin sudah terinfeksi JOI Virus.

  Perhatikan bahwa periode waktu terakhir suatu hari dan periode waktu pertama hari berikutnya berkesinambungan.

Untuk keperluan eksperimen, kita ingin menginfeksi setidaknya 1 penduduk, tetapi tidak ingin menginfeksi terlalu banyak penduduk. Pada awalnya, kita memilih 1 penduduk sebagai orang pertama yang terinfeksi dan menginfeksinya dengan JOI Virus. Penduduk dengan ketahanan $0$ tidak dapat dipilih sebagai orang pertama yang terinfeksi.

Diberikan arah asal angin pada setiap periode waktu dan ketahanan setiap penduduk, tulislah program yang menghitung jumlah minimum penduduk yang terinfeksi setelah $10^{100}$ hari, serta banyaknya penduduk yang menghasilkan jumlah minimum tersebut jika dipilih sebagai orang pertama yang terinfeksi.

Masukan

Baca data berikut dari masukan standar.

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

$D$ adalah string dengan panjang $M$ yang menyatakan arah asal angin di IOI Island. $D$ terdiri dari 4 jenis karakter: N, S, W, atau E. Karakter ke-$k$ ($1 \le k \le M$) menyatakan arah asal angin pada periode waktu $k$. Perhatikan bahwa ini bukan arah tujuan angin bertiup. N menyatakan utara, S menyatakan selatan, W menyatakan barat, dan E menyatakan timur.

Keluaran

Tuliskan dua baris ke keluaran standar.

Baris pertama harus berisi jumlah minimum penduduk yang terinfeksi setelah $10^{100}$ hari. Baris kedua harus berisi banyaknya penduduk yang menghasilkan jumlah minimum penduduk terinfeksi jika dipilih sebagai orang pertama yang terinfeksi.

Batasan

• $1 \le M \le 100\,000$.
• $1 \le R \le 800$.
• $1 \le C \le 800$.
• $D$ adalah string dengan panjang $M$ yang hanya berisi N, S, W, dan E.
• $0 \le U_{i,j} \le 100\,000$ ($1 \le i \le R$, $1 \le j \le C$).
• Terdapat setidaknya 1 pasangan $(i,j)$ yang memenuhi $1 \le U_{i,j}$ ($1 \le i \le R$, $1 \le j \le C$).

Subtugas

1. (14 poin) $D$ hanya berisi W dan E.
2. (6 poin) $1 \le R \le 50$, $1 \le C \le 50$.
3. (80 poin) Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

8
8

Penjelasan

Mari kita pertimbangkan keadaan ketika penduduk $(3,1)$ dipilih sebagai orang pertama yang terinfeksi.

• Untuk penduduk $(2,1)$, pada periode waktu 1 hari ke-1, angin bertiup dari selatan dan penduduk tetangga di selatan sudah terinfeksi, sehingga ia akan terinfeksi mulai periode waktu 2 hari ke-1.
• Untuk penduduk $(3,2)$, pada periode waktu 2 hari ke-1, angin bertiup dari barat dan penduduk tetangga di barat sudah terinfeksi, sehingga ia akan terinfeksi mulai periode waktu 3 hari ke-1.
• Untuk penduduk $(1,1)$, pada periode waktu 6 hari ke-1, angin bertiup dari selatan dan penduduk tetangga di selatan sudah terinfeksi; pada periode waktu 1 hari ke-2, angin juga bertiup dari selatan dan penduduk tetangga di selatan sudah terinfeksi, sehingga ia akan terinfeksi mulai periode waktu 2 hari ke-2.
• Untuk penduduk $(1,2)$, pada periode waktu 2 hari ke-2, angin bertiup dari barat dan penduduk tetangga di barat sudah terinfeksi, sehingga ia akan terinfeksi mulai periode waktu 3 hari ke-2.
• Untuk penduduk $(1,3)$, pada periode waktu 2 hari ke-3, angin bertiup dari barat dan penduduk tetangga di barat sudah terinfeksi, sehingga ia akan terinfeksi mulai periode waktu 3 hari ke-3.
• Untuk penduduk $(2,3)$, pada periode waktu 3 hari ke-3, angin bertiup dari utara dan penduduk tetangga di utara sudah terinfeksi, sehingga ia akan terinfeksi mulai periode waktu 4 hari ke-3.
• Untuk penduduk $(3,3)$, pada periode waktu 2 hari ke-4, angin bertiup dari barat dan penduduk tetangga di barat sudah terinfeksi; pada periode waktu 3 hari ke-4, angin bertiup dari utara dan penduduk tetangga di utara sudah terinfeksi, sehingga ia akan terinfeksi mulai periode waktu 4 hari ke-4.

Tidak ada lagi penduduk yang akan terinfeksi JOI Virus. Jadi, jika penduduk $(3,1)$ dipilih sebagai orang pertama yang terinfeksi, 8 penduduk akan terinfeksi JOI Virus setelah $10^{100}$ hari.

Siapa pun yang dipilih sebagai orang pertama yang terinfeksi, jumlah penduduk yang terinfeksi JOI Virus setelah $10^{100}$ hari tidak dapat dibuat kurang dari 8, sehingga Anda harus mengeluarkan 8 pada baris pertama. Jika penduduk $(1,1)$, $(1,2)$, $(1,3)$, $(2,1)$, $(2,3)$, $(3,1)$, $(3,2)$, atau $(3,3)$ dipilih sebagai orang pertama yang terinfeksi, jumlah penduduk yang terinfeksi setelah $10^{100}$ hari adalah 8, sehingga Anda harus mengeluarkan 8 pada baris kedua.

Masukan 2

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

Keluaran 2

3
3

Penjelasan

Contoh masukan dan keluaran ini memenuhi batasan Subtugas 1.