Hãy điều khiển C-Bot mang theo súng laser đến một bãi thiên thạch, là một khu vực hình chữ nhật gồm \(M\) hàng, \(N\) cột. Các khối đá có dạng hình lập phương giống hệt nhau, được xếp chồng lên nhau thành từng cột đá. Ở ô thuộc hàng \(i\), cột \(j\) (\(1 \le i \le M, 1 \le j \le N\)), số khối đá xếp chồng là \(a_{i,j}\) (tính từ mặt đất lên).

C-Bot có thể di chuyển ra một trong bốn phía của bãi thiên thạch (phía trước, phía sau, phía trái, phía phải). Rồi bắn một tia laser xuyên thẳng và vuông góc với một mặt của khối đá, theo một hàng hoặc một cột dựa vào lệnh chỉ hướng bắn như sau:

• W: bắn tại một hàng, từ trái sang phải.
• E: bắn tại một hàng, từ phải sang trái.
• N: bắn tại một cột, từ trước ra sau.
• S: bắn tại một cột, từ sau ra trước.

Khi bắn, bắt đầu từ phía gần C-Bot nhất, tia laser sẽ lần lượt phá hủy đủ \(R\) khối đá đầu tiên nằm ở độ cao \(h\) của các cột đá có chiều cao ít nhất bằng \(h\). Những cột đá có chiều cao thấp hơn \(h\) sẽ không bị ảnh hưởng bởi phát bắn đó. Khi một khối đá bị phá hủy, các khối đá ở phía trên của cùng cột đá đó sẽ rơi xuống lấp đầy khoảng trống.

Yêu cầu: C-Bot phải thực hiện \(K\) phát bắn được ghi trên thẻ để bãi thiên thạch đạt trạng thái ổn định. Sau đó, C-Bot sẽ được thu thập (một lần duy nhất) các khối đá trong khu vực hình vuông kích thước \(P \times P\). Hãy cho biết số khối đá lớn nhất mà C-Bot mang về được.

Input

• Dòng đầu tiên gồm năm số nguyên \(M, N, R, K, P\) (\(1 \le M \cdot N \le 10^6\); \(1 \le R \le 10\); \(1 \le K \le 3 \cdot 10^5\); \(1 \le P \le \min(M, N, 10)\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên dương mô tả số khối đá ban đầu tại mỗi ô (\(a_{i,j} \le 10^6\)).
• \(K\) dòng cuối cùng, mỗi dòng mô tả một phát bắn laser, gồm:
  • Một ký tự trong {W, E, N, S} chỉ hướng bắn.
  • Hai số nguyên \(id\) và \(h\) (\(1 \le h \le 10^6\)):
    • Nếu hướng là W hoặc E, \(id\) là chỉ số hàng (từ \(1\) đến \(M\)).
    • Nếu hướng là N hoặc S, \(id\) là chỉ số cột (từ \(1\) đến \(N\)).

Output

• Dòng đầu tiên ghi số nguyên là số khối đá lớn nhất C-Bot mang về được.

Example

4 8 2 6 2
1 1 1 1 1 1 1 1
1 2 3 1 1 1 3 1
1 2 1 1 3 1 1 1
1 1 1 1 1 1 1 2
N 2 2
W 2 2
W 2 3
E 2 1
S 4 1
S 7 1

6

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Tất cả phát bắn ở độ cao \(h = 1, M \cdot N \le 10^4\) và \(K \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): Tất cả phát bắn ở độ cao \(h = 1, M \cdot N \le 10^6\) và \(K \le 10^5\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.