UFO

스네이크랜드 보안대가 적대적인 외계 우주선에 손상을 입혀 강제로 착륙시켰다. 우주선은 한 변이 1인 정육면체 구획을 쌓아 만들었다. 위에서 내려다보면 우주선은 $N$행 $M$열 격자를 덮고, $i$행 $j$열 칸 위에는 구획이 $h_{i,j}$개 쌓여 있다. 층은 바닥부터 1층으로 세므로, $i$행 $j$열 칸에 $L$층 구획이 있다는 말은 $h_{i,j} \ge L$이라는 뜻이다.

구획은 레이저로만 잘리는 금속으로 만들었다. 우주선의 네 면에 각각 레이저 장치가 있고, 각 장치는 자기 면에 수직인 빔을 쏜다. 빔은 한 행이나 한 열을 따라 정해진 한 층의 높이로 수평으로 나아간다.

1행이 가장 북쪽 행이고 1열이 가장 서쪽 열이다. 서쪽에서 쏜 빔은 그 행을 1열에서 $M$열 쪽으로 지나가고, 동쪽에서 쏜 빔은 $M$열에서 1열 쪽으로 지나간다. 북쪽에서 쏜 빔은 그 열을 1행에서 $N$행 쪽으로, 남쪽에서 쏜 빔은 $N$행에서 1행 쪽으로 지나간다.

빔은 지나가는 길에서 앞에 있는 구획부터 최대 $R$개를 부순다. 진행 방향으로 칸을 하나씩 보면서, 그 칸의 더미가 쏘는 층까지 아직 닿아 있으면 그 층의 구획을 부수고, 부순 개수가 $R$개가 되면 멈춘다. 부서진 구획 위에 있던 구획은 한 층씩 내려앉으므로, 한 칸에서 구획을 하나 부수면 그 칸의 더미 높이가 1 줄어든다. $R$개를 다 부수기 전에 빔이 우주선을 빠져나가면 부순 개수는 그보다 적다.

$K$번 사격한 뒤에 우주선을 공중에서 폭격한다. 폭탄은 격자에 맞춘 $P$행 $P$열 정사각형 영역을 덮고, 그 $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$열 칸에 쌓인 구획의 개수 $h_{i,j}$이다 ($1 \le h_{i,j} \le 10^6$).

다음 $K$개 줄에는 사격이 한 줄에 하나씩 주어진다. 각 줄은 문자 하나와 정수 두 개로 이루어진다. 문자는 빔이 오는 방향으로 W, E, S, N 중 하나이다. W나 E이면 첫 번째 정수는 1 이상 $N$ 이하의 행 번호이고, N이나 S이면 1 이상 $M$ 이하의 열 번호이다. 두 번째 정수는 쏘는 층으로 1 이상 $10^6$ 이하이다. 사격은 주어진 순서대로 처리한다.

$K$번의 사격이 끝난 뒤 어떤 $P \times P$ 칸 영역 위에 남아 있는 구획 개수의 최댓값을 출력한다.