UFO Batch 컴파일 명령

지구 방위대는 외계인들의 우주선을 파괴할 필요가 있습니다. 그들은 이미 우주선에 큰 손상을 입혀 사막에 착지하게 헀습니다. 이 우주선은 단위 큐브로 만들어졌으며 바닥은 $N \times M$ 크기의 직사각형 형태를 가지고 있습니다. 임의의 한 $N=4, M=8$짜리 우주선을 위에서 바라본 모습은 아래 그림에서 볼 수 있습니다.

이 우주선은 엄청 강한 금속으로 지어졌기 때문에, 이를 파괴하기 위해 레이저가 사용되었습니다. 레이저 건들은 우주선의 네 변을 향해 놓여 있으며, 이들은 우주선의 특정 블럭들로 레이저 광선을 발사합니다. (광선은 항상 우주선의 네 변과 수직하도록 발사되며 높이(고도)는 일정합니다) 각 광선은 가다가 만나는 최초의 $R$개 블럭들을 파괴합니다. 만약 파괴된 블럭 위에 다른 블럭들이 쌓여 있다면, 이들은 아래로 움직입니다.

광선을 $K$번 발사한 이후 지구 방위대는 우주선에 공습하기로 결정되었습니다. 이들은 파괴되지 않은 블럭들의 개수가 가장 많은 우주선 내부의 $P \times P$ 영역을 선택한 뒤, 이 영역 안의 모든 블럭을 파괴할 것입니다.

지구 방위대가 공습하여 파괴할 수 있는 가장 많은 블럭의 수를 계산하는 프로그램을 계산하세요.

입력 형식

첫 번째 줄에 $N, M (1 \le N \times M \le 1 000 000), R (0 < R \le 10), K (0 < K \le 300 000), P (0 < P \le \min(N,M,10)$이 주어집니다. 다음 $N$개 줄에는 $M$개의 숫자가 주어집니다. 이들 중 $i$번째 줄의 $j$번째 숫자는 우주선 바닥의 $i$행 $j$열 위에 쌓여 있는 블럭의 수를 나타냅니다. 각 숫자는 $1$ 이상 $10^{6}$ 이하입니다.

다음 $K$개 줄에는 광선 발사에 대한 정보가 주어집니다. 이 줄들에는 하나의 문자와 두 개의 문자가 공백을 사이로 두고 주어집니다. 문자는 레이저를 발사하는 위치을 나타냅니다: "W"는 서쪽, "E"는 동쪽, "S"는 남쪽, "N"는 북쪽의 위치에서 반대 방향으로 발사한다는 의미입니다. 첫 번째 숫자는 발사 방향이 서쪽 또는 동쪽이라면 발사할 위치의 행 번호, 북쪽 또는 남쪽이라면 발사할 위치의 열 번호입니다. 두 번째 숫자는 광선을 발사할 높이입니다. 행과 열 번호는 $1$부터 차례대로 자연수 번호가 매겨집니다. 여기서 주어지는 모든 정수들은 $1$ 이상 $10^{6}$ 이하입니다.

출력 형식

레이저를 $K$번 쏜 이후, 공습으로 파괴할 수 있는 가장 많은 블럭의 개수 (파괴되지 않은 블럭의 개수가 가장 많은 $P \times P$ 영역을 파괴해야 합니다.) 를 출력합니다.

채점

각 테스트 케이스마다 점수가 주어집니다.

• 30%의 테스트 케이스에 대해 $1 \le N \times M \le 50 000, 0 < K \le 5 000.$
• 또다른 30%의 테스트 케이스에 대해 모든 레이저는 높이 1에서 발사되며, $1 \le N \times M \le 1 000 000, 0 < K \le 300 000.$

예제

참고

위 그림에서 예제대로 레이저를 모두 발사한 이후 우주선의 상태를 볼 수 있습니다.