คุณรู้จักบริษัท Just Odd Inventions Co., Ltd. หรือไม่? ธุรกิจของบริษัทนี้คือการสร้าง “สิ่งประดิษฐ์ที่แปลกเท่านั้น” ในที่นี้จะเรียกสั้น ๆ ว่าบริษัท JOI

บริษัท JOI พัฒนาไวรัสชนิดใหม่ชื่อ “JOI Virus” และต้องการทดลองโดยทำให้ผู้อยู่อาศัยบนเกาะ IOI ติดไวรัสนี้

เกาะ IOI มีรูปร่างเป็นสี่เหลี่ยมผืนผ้า มีถนนขนานกัน $R-1$ สายจากตะวันออกไปตะวันตก และถนนขนานกัน $C-1$ สายจากเหนือไปใต้ ถนนเหล่านี้แบ่งเกาะออกเป็น $RC$ ส่วน แต่ละส่วนมีผู้อยู่อาศัยหนึ่งคนพอดี เราเรียกผู้ที่อยู่ในส่วนลำดับที่ $i$ จากเหนือและลำดับที่ $j$ จากตะวันตก ($1 \le i \le R$, $1 \le j \le C$) ว่า “ผู้อยู่อาศัย $(i,j)$”

บนเกาะ IOI แต่ละวันแบ่งเป็น $M$ ช่วงเวลา เราเรียกช่วงเวลาลำดับที่ $k$ ว่า “ช่วงเวลา $k$” ลมพัดมาจากทิศใดทิศหนึ่งเสมอ ได้แก่ เหนือ ใต้ ตะวันออก หรือตะวันตก ทิศอาจเปลี่ยนไปตามช่วงเวลา แต่ในช่วงเวลาเดียวกัน ลมจะพัดมาจากทิศเดียวกันไม่ว่าจะเป็นวันใด

ผู้อยู่อาศัยทุกคนมีค่า “ความต้านทาน” ความต้านทานของผู้อยู่อาศัย $(i,j)$ ($1 \le i \le R$, $1 \le j \le C$) แทนด้วยจำนวนเต็มไม่เป็นลบ $U_{i,j}$

• ถ้า $U_{i,j}=0$ หมายความว่าผู้อยู่อาศัย $(i,j)$ มีความต้านทานสูง และจะไม่ติด JOI Virus

• ถ้า $U_{i,j}$ เป็นจำนวนเต็มบวก หมายความว่าผู้อยู่อาศัย $(i,j)$ อาจติด JOI Virus หากเงื่อนไขต่อไปนี้เป็นจริงต่อเนื่องกัน $U_{i,j}$ ช่วงเวลา ผู้นั้นจะติดเชื้อตั้งแต่ช่วงเวลาถัดไป:

  • ผู้อยู่อาศัยในส่วนที่ติดกันทางทิศที่ลมพัดมานั้นติด JOI Virus แล้ว

  โปรดทราบว่าช่วงเวลาสุดท้ายของวันกับช่วงเวลาแรกของวันถัดไปถือว่าต่อเนื่องกัน

เพื่อให้บรรลุวัตถุประสงค์ของการทดลอง เราต้องการให้มีผู้ติดเชื้ออย่างน้อยหนึ่งคน แต่ไม่ต้องการให้มีผู้ติดเชื้อมากเกินไป ในตอนเริ่มต้น เราเลือกผู้อยู่อาศัยหนึ่งคนเป็นผู้ติดเชื้อคนแรก และทำให้ผู้นั้นติด JOI Virus เราเลือกผู้ที่มีความต้านทานเท่ากับ $0$ เป็นผู้ติดเชื้อคนแรกไม่ได้

กำหนดทิศที่ลมพัดมาในแต่ละช่วงเวลาและความต้านทานของผู้อยู่อาศัยแต่ละคน จงเขียนโปรแกรมคำนวณจำนวนผู้ติดเชื้อที่น้อยที่สุดหลังจาก $10^{100}$ วัน และจำนวนผู้อยู่อาศัยที่เมื่อเลือกเป็นผู้ติดเชื้อคนแรกแล้วทำให้ได้จำนวนผู้ติดเชื้อที่น้อยที่สุดนั้น

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

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

$D$ เป็นสตริงความยาว $M$ ที่บอกทิศที่ลมพัดมาบนเกาะ IOI ประกอบด้วยอักขระ 4 ชนิด ได้แก่ N, S, W หรือ E อักขระที่ $k$ ($1 \le k \le M$) บอกทิศที่ลมพัดมาในช่วงเวลา $k$ โปรดทราบว่านี่ไม่ใช่ทิศที่ลมพัดไป N หมายถึงเหนือ S หมายถึงใต้ W หมายถึงตะวันตก และ E หมายถึงตะวันออก

ข้อมูลส่งออก

เขียนข้อมูลสองบรรทัดไปยังข้อมูลส่งออกมาตรฐาน

บรรทัดแรกให้เขียนจำนวนผู้ติดเชื้อที่น้อยที่สุดหลังจาก $10^{100}$ วัน บรรทัดที่สองให้เขียนจำนวนผู้อยู่อาศัยที่เมื่อเลือกเป็นผู้ติดเชื้อคนแรกแล้วทำให้ได้จำนวนผู้ติดเชื้อที่น้อยที่สุดนั้น

ข้อจำกัด

• $1 \le M \le 100\,000$
• $1 \le R \le 800$
• $1 \le C \le 800$
• $D$ เป็นสตริงความยาว $M$ ที่ประกอบด้วย N, S, W และ E เท่านั้น
• $0 \le U_{i,j} \le 100\,000$ ($1 \le i \le R$, $1 \le j \le C$)
• มีอย่างน้อยหนึ่งคู่ $(i,j)$ ที่ $1 \le U_{i,j}$ ($1 \le i \le R$, $1 \le j \le C$)

งานย่อย

1. (14 คะแนน) $D$ มีเพียง W และ E
2. (6 คะแนน) $1 \le R \le 50$, $1 \le C \le 50$
3. (80 คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

8
8

หมายเหตุ

พิจารณากรณีเลือกผู้อยู่อาศัย $(3,1)$ เป็นผู้ติดเชื้อคนแรก

• สำหรับผู้อยู่อาศัย $(2,1)$ ในช่วงเวลา $1$ ของวันที่ $1$ ลมพัดมาจากใต้และเพื่อนบ้านทางใต้ติดเชื้อแล้ว ผู้นี้จึงติดเชื้อตั้งแต่ช่วงเวลา $2$ ของวันที่ $1$
• สำหรับผู้อยู่อาศัย $(3,2)$ ในช่วงเวลา $2$ ของวันที่ $1$ ลมพัดมาจากตะวันตกและเพื่อนบ้านทางตะวันตกติดเชื้อแล้ว ผู้นี้จึงติดเชื้อตั้งแต่ช่วงเวลา $3$ ของวันที่ $1$
• สำหรับผู้อยู่อาศัย $(1,1)$ ในช่วงเวลา $6$ ของวันที่ $1$ ลมพัดมาจากใต้และเพื่อนบ้านทางใต้ติดเชื้อแล้ว และในช่วงเวลา $1$ ของวันที่ $2$ ลมก็พัดมาจากใต้และเพื่อนบ้านทางใต้ติดเชื้อแล้ว ผู้นี้จึงติดเชื้อตั้งแต่ช่วงเวลา $2$ ของวันที่ $2$
• สำหรับผู้อยู่อาศัย $(1,2)$ ในช่วงเวลา $2$ ของวันที่ $2$ ลมพัดมาจากตะวันตกและเพื่อนบ้านทางตะวันตกติดเชื้อแล้ว ผู้นี้จึงติดเชื้อตั้งแต่ช่วงเวลา $3$ ของวันที่ $2$
• สำหรับผู้อยู่อาศัย $(1,3)$ ในช่วงเวลา $2$ ของวันที่ $3$ ลมพัดมาจากตะวันตกและเพื่อนบ้านทางตะวันตกติดเชื้อแล้ว ผู้นี้จึงติดเชื้อตั้งแต่ช่วงเวลา $3$ ของวันที่ $3$
• สำหรับผู้อยู่อาศัย $(2,3)$ ในช่วงเวลา $3$ ของวันที่ $3$ ลมพัดมาจากเหนือและเพื่อนบ้านทางเหนือติดเชื้อแล้ว ผู้นี้จึงติดเชื้อตั้งแต่ช่วงเวลา $4$ ของวันที่ $3$
• สำหรับผู้อยู่อาศัย $(3,3)$ ในช่วงเวลา $2$ ของวันที่ $4$ ลมพัดมาจากตะวันตกและเพื่อนบ้านทางตะวันตกติดเชื้อแล้ว และในช่วงเวลา $3$ ของวันที่ $4$ ลมพัดมาจากเหนือและเพื่อนบ้านทางเหนือติดเชื้อแล้ว ผู้นี้จึงติดเชื้อตั้งแต่ช่วงเวลา $4$ ของวันที่ $4$

จะไม่มีผู้อยู่อาศัยติด JOI Virus เพิ่มอีก ดังนั้น เมื่อเลือกผู้อยู่อาศัย $(3,1)$ เป็นผู้ติดเชื้อคนแรก จะมีผู้ติด JOI Virus $8$ คนหลังจาก $10^{100}$ วัน

ไม่ว่าจะเลือกใครเป็นผู้ติดเชื้อคนแรก ก็ทำให้จำนวนผู้ติด JOI Virus หลังจาก $10^{100}$ วันน้อยกว่า $8$ ไม่ได้ จึงต้องส่งออก $8$ ในบรรทัดแรก ถ้าเลือกผู้อยู่อาศัย $(1,1)$, $(1,2)$, $(1,3)$, $(2,1)$, $(2,3)$, $(3,1)$, $(3,2)$ หรือ $(3,3)$ เป็นผู้ติดเชื้อคนแรก จะมีผู้ติดเชื้อ $8$ คนหลังจาก $10^{100}$ วัน จึงต้องส่งออก $8$ ในบรรทัดที่สอง

ข้อมูลนำเข้า 2

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

ข้อมูลส่งออก 2

3
3

หมายเหตุ

ข้อมูลนำเข้าและข้อมูลส่งออกตัวอย่างนี้เป็นไปตามข้อจำกัดของงานย่อย 1