Bài 6. Xử lý môi trường (CLEAN)

Các nhà máy sản xuất các thiết bị của tập đoàn Space X thường được đặt ở những vùng đất đặc biệt. Nhà máy sản xuất các mảnh ghép được xây dựng trên một vùng diện tích có dạng hình chữ nhật \(m\times n\) bằng cách xếp chồng các khối vật liệu lên nhau, khối vật liệu là một khối lập phương đơn vị có kích thước \((1\times1\times1)\). Các khối vật liệu của nhà máy được chế tạo từ hợp kim vững chắc để chống chịu các tác động của thiên tai khắc nghiệt. Khi kết thúc hoạt động của nhà máy, tập đoàn phải phá hủy nhà máy để trả lại nguyên trạng vùng đất ban đầu. Để làm được điều đó, tập đoàn phải phá hủy các khối vật liệu ban đầu được dùng để xây dựng nhà máy; các khối vật liệu được phá hủy bằng cách bắn tia laser vào nó.

Máy bắn tia laser được lắp đặt ở bốn phía của nhà máy, và chúng được thiết lập để bắn tia laser vào một số khối vật liệu của nhà máy (tia laser luôn vuông góc với các mặt của nhà máy). Mỗi tia laser phá hủy \(r\) khối đầu tiên trên đường đi của nó. Nếu có một hoặc nhiều khối trên đỉnh của khối bị phá hủy, chúng sẽ di chuyển thẳng xuống. Sau khi bắn \(k\) tia laser, tập đoàn quyết định thực hiện một cuộc phá hủy trên diện rộng. Họ quyết định chọn khu vực có kích thước \(p\times p\) trên nhà máy sao cho số lượng khối vật liệu bị phá hủy là nhiều nhất có thể; các tia laser sẽ được bố trí phù hợp để phá hủy tất cả các khối vật liệu trong khu vực này.

Tìm số lượng khối vật liệu tối đa bị phá hủy trong khu vực có kích thước \(p\times p\) sau khi thực hiện \(k\) phát bắn.

Input

Cho trong file CLEAN.INP, có cấu trúc:

• Dòng 1: Chứa năm số nguyên \(m,n,r,k,p\).

• Trên \(m\) dòng tiếp theo: Mỗi dòng chứa \(n\) số; số \(a_{i,j}\) ở dòng thứ \(i\), cột thứ \(j\) là số khối lập phương đơn vị được xếp chồng lên nhau ở vị trí \((i,j)\) \((1 \le a_{i,j} \le 10^6)\).
• Trên \(k\) dòng tiếp theo mô tả các phát bắn laser, có dạng dir i h:
• dir là một trong bốn chữ cái, mô tả hướng bắn: W — hướng Tây, E — hướng Đông, S — hướng Nam, N — hướng Bắc.
• \(i\) là một số nguyên dương. Nếu hướng bắn là hướng Đông hoặc hướng Tây thì đây là chỉ số dòng; nếu hướng bắn là hướng Nam hoặc hướng Bắc thì đây là chỉ số cột bị bắn \((1 \le i \le 10^6)\).
• \(h\) là độ cao của phát bắn \((1 \le h \le 10^6)\).

Output

Ghi ra file CLEAN.OUT:

• Dòng 1: Ghi một số nguyên duy nhất là kết quả bài toán.

Example

Scoring

• 30% số test ứng với 30% số điểm có \(n\times m \le 300\).
• 70% số test ứng với 70% số điểm không có ràng buộc gì thêm.