UFO

사막에 불시착한 외계 우주선을 파괴해야 한다. 우주선은 단위 정육면체 블록으로 이루어져 있고, 바닥 층은 $N \times M$ 직사각형이다. 이 직사각형의 $(i, j)$ 칸에는 블록이 여러 개 쌓여 있으며, 각 칸의 층은 바닥부터 $1$층, $2$층 순으로 번호를 매긴다. 행 번호는 북쪽에서 남쪽으로 $1$부터 $N$까지이고, 열 번호는 서쪽에서 동쪽으로 $1$부터 $M$까지이다. 아래 그림은 $N = 4$, $M = 8$인 우주선을 위에서 본 모습이다.

블록은 레이저로만 자를 수 있는 금속이라서 우주선 네 면에 레이저포를 설치했다. 레이저는 발사한 면에 수직이고 지면과 평행하게, 정해진 한 층을 따라 날아간다.

발사 한 번은 면, 번호, 높이 $h$로 정해진다. 서쪽에서 쏜 레이저는 지정된 행을 따라 $1$열에서 $M$열 방향으로 나아가고, 동쪽에서 쏜 레이저는 같은 행을 $M$열에서 $1$열 방향으로 나아간다. 북쪽에서 쏜 레이저는 지정된 열을 따라 $1$행에서 $N$행 방향으로 나아가고, 남쪽에서 쏜 레이저는 같은 열을 $N$행에서 $1$행 방향으로 나아간다.

레이저는 그 직선 위의 칸을 하나씩 지난다. 지나는 칸에 블록이 $h$개 이상 쌓여 있으면 $h$층의 블록을 파괴하고, 그 위에 있던 블록은 한 층씩 내려앉아 그 칸의 높이가 $1$만큼 줄어든다. 한 칸에서 파괴되는 블록은 최대 한 개이며, 레이저는 곧바로 다음 칸으로 나아간다. 블록이 $h$개보다 적게 쌓인 칸은 그대로 통과한다. 레이저는 블록을 $R$개 파괴하면 멈추고, 그전에 우주선을 벗어나도 멈춘다.

$K$번의 발사가 끝난 뒤 $P \times P$ 크기의 정사각형 구역에 공습을 가한다. 남아 있는 블록이 가장 많은 구역을 골라 그 안의 블록을 모두 파괴한다. 공습으로 파괴하는 블록의 최대 개수를 구하라.

첫째 줄에 정수 $N$, $M$, $R$, $K$, $P$가 주어진다 ($1 \le N \times M \le 10^6$, $1 \le R \le 10$, $1 \le K \le 3 \times 10^5$, $1 \le P \le \min(N, M, 10)$).

다음 $N$개 줄에는 각각 $M$개의 정수가 주어진다. $i$번째 줄의 $j$번째 수는 $(i, j)$ 칸에 쌓인 블록의 개수이고, $1$ 이상 $10^6$ 이하이다.

다음 $K$개 줄에는 발사 정보가 한 줄에 하나씩, 문자 하나와 정수 두 개가 공백으로 구분되어 주어진다. 문자는 서쪽이면 W, 동쪽이면 E, 남쪽이면 S, 북쪽이면 N이다. W와 E는 첫 번째 정수가 $1$ 이상 $N$ 이하의 행 번호이고, N과 S는 $1$ 이상 $M$ 이하의 열 번호이다. 두 번째 정수는 발사 높이이고 $1$ 이상 $10^6$ 이하이다.

$K$번의 발사가 끝난 뒤 $P \times P$ 구역에 남아 있는 블록 개수의 최댓값을 출력한다.

첫 번째 예제의 발사를 모두 끝낸 뒤 우주선의 모습이다. 색칠한 정사각형이 블록이 가장 많이 남은 $2 \times 2$ 구역이다.