Cơ quan an ninh Trái Đất cần phải tiêu diệt tàu vũ trụ của người ngoài hành tinh để bảo vệ hòa bình cho Trái Đất. Tàu vũ trụ hiện đang hạ cánh trên sa mạc Sahara để thực hiện việc cướp nhiên liệu. May thay, đây là một trận địa đã được chuẩn bị trước đó của người Trái Đất.

Tàu vũ trụ được xây dựng từ các khối lập phương đơn vị kích thước ~1 \times 1 \times 1~ xếp chồng lên nhau, và lớp dưới cùng có dạng hình chữ nhật ~m \times n~.

Trận địa được bao phủ bởi rất nhiều máy bắn tia laser để phá hủy con tàu. Súng laser được lắp đặt ở bốn phía của tàu vũ trụ, và chúng định kì bắn tia laser vào một số khối của con tàu. Mỗi tia luôn vuông góc với các mặt của tàu vũ trụ và 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 xuống.

Sau khi bắn ~k~ phát, cơ quan an ninh quyết định thực hiện một cuộc không kích diện rộng. Họ chọn khu vực có kích thước ~p \times p~ trên con tàu sao cho số lượng khối lập phương đơn vị bị phá hủy là nhiều nhất có thể. Cuộc không kích sẽ phá hủy tất cả các khối trong khu vực này.

Hãy tìm số lượng khối tối đa bị phá hủy bởi cuộc không kích phạm vi ~p \times p~ sau ~k~ phát bắn laser.

Input

• Dòng thứ nhất chứa năm số nguyên ~m, n, r, k, p~ (~1 \le m \times n \le 10^6; 1 \le r \le 10; 1 \le k \le 3 \times 10^5; 1 \le p \le \min(m, n, 10)~).
• ~m~ dòng tiếp theo, mỗi dòng chứa ~n~ số; số ở dòng thứ ~i~, cột thứ ~j~ là ~a_{i,j}~, 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~).
• ~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: 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.
  • ~h~ là độ cao của phát bắn.

Output

Một dòng chứa một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask 1 (30% số điểm): Dữ liệu nhỏ theo đề gốc.
• Subtask 2 (70% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

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

Output

6