Công ty Just Odd Inventions, gọi tắt là công ty JOI, chuyên tạo ra những phát minh kỳ lạ. Công ty vừa phát triển một loại vi-rút mới mang tên JOI Virus và muốn tiến hành thí nghiệm bằng cách cho cư dân trên đảo IOI nhiễm vi-rút này.

Đảo IOI có hình chữ nhật. Có \(R-1\) con đường song song chạy theo hướng đông-tây và \(C-1\) con đường song song chạy theo hướng bắc-nam, chia đảo thành \(RC\) ô. Mỗi ô có đúng một cư dân. Cư dân ở ô thứ \(i\) tính từ phía bắc và thứ \(j\) tính từ phía tây được gọi là cư dân \((i,j)\).

Mỗi ngày trên đảo được chia thành \(M\) khoảng thời gian, đánh số từ \(1\) đến \(M\). Gió luôn thổi từ một trong bốn hướng bắc, nam, đông hoặc tây. Hướng gió có thể thay đổi theo khoảng thời gian, nhưng tại cùng một khoảng thời gian trong ngày thì hướng gió giống nhau ở mọi ngày.

Mỗi cư dân \((i,j)\) có mức kháng vi-rút là số nguyên không âm \(U_{i,j}\):

• Nếu \(U_{i,j}=0\), cư dân này có sức đề kháng cao và không bao giờ nhiễm JOI Virus.
• Nếu \(U_{i,j}>0\), cư dân này có thể nhiễm JOI Virus. Nếu điều kiện sau được duy trì trong \(U_{i,j}\) khoảng thời gian liên tiếp, cư dân này sẽ nhiễm vi-rút kể từ khoảng thời gian tiếp theo: cư dân ở ô kề theo hướng mà gió thổi từ đó đến đã nhiễm JOI Virus.

Khoảng thời gian cuối cùng của một ngày và khoảng thời gian đầu tiên của ngày kế tiếp được tính là liên tiếp. Hướng gió trong chuỗi khoảng thời gian liên tiếp nói trên không nhất thiết phải giữ nguyên.

Để phục vụ thí nghiệm, công ty muốn có ít nhất một người nhiễm nhưng không muốn quá nhiều người nhiễm. Ban đầu, công ty chọn đúng một cư dân làm người nhiễm đầu tiên và cho người đó nhiễm JOI Virus. Không được chọn người có mức kháng vi-rút bằng \(0\).

Cho hướng gió trong từng khoảng thời gian và mức kháng vi-rút của từng cư dân, hãy tính số người nhiễm ít nhất sau \(10^{100}\) ngày, cùng số cách chọn người nhiễm đầu tiên để đạt được số người nhiễm ít nhất đó.

Dữ liệu vào

• Dòng đầu chứa \(M,R,C\).
• Dòng thứ hai chứa chuỗi \(D\) độ dài \(M\).
• Trong \(R\) dòng tiếp theo, dòng thứ \(i\) chứa \(U_{i,1},\ldots,U_{i,C}\).

Dữ liệu được đọc từ đầu vào chuẩn. Ký tự thứ \(k\) của \(D\) cho biết hướng mà gió thổi từ đó đến trong khoảng thời gian \(k\), không phải hướng gió thổi tới. Các ký tự N, S, W, E lần lượt chỉ bắc, nam, tây, đông.

Dữ liệu ra

Ghi hai dòng ra đầu ra chuẩn:

• Dòng thứ nhất chứa số người nhiễm ít nhất sau \(10^{100}\) ngày.
• Dòng thứ hai chứa số cư dân mà khi chọn làm người nhiễm đầu tiên sẽ đạt được số người nhiễm ít nhất đó.

Ràng buộc

• \(1\le M\le 100\,000\).
• \(1\le R\le 800\).
• \(1\le C\le 800\).
• \(D\) có độ dài \(M\) và chỉ gồm các ký tự N, S, W, E.
• \(0\le U_{i,j}\le 100\,000\) với \(1\le i\le R\), \(1\le j\le C\).
• Có ít nhất một cặp \((i,j)\) với \(1\le i\le R\), \(1\le j\le C\) và \(U_{i,j}\ge 1\).

Phân nhóm

1. \(14\) điểm: \(D\) chỉ gồm các ký tự W và E.
2. \(6\) điểm: \(1\le R\le 50\), \(1\le C\le 50\).
3. \(80\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

8
8

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

3
3

Nguồn

JOI Open Contest 2019, bài Virus Experiment (virus), ngày 14/7/2019. Bản dịch từ đề tiếng Anh chính thức của JCIOI, theo giấy phép CC BY-SA 4.0.