Snakeland 的安全部门想要摧毁敌对的外星飞船。安全部门已经击伤了飞船并迫使其着陆。飞船由单位大小的立方体舱室建成。第一层总是由 $N \times M$ 个舱室组成。左图显示了一个大小为 $N = 4, M = 8$ 的飞船示例，右图显示了该飞船的俯视图，其中标明了重叠（堆叠）的舱室数量。

舱室由超强金属制成，因此需要使用激光来摧毁飞船。激光装置部署在飞船的四个侧面，它们定期向飞船的不同舱室发射垂直于飞船侧面的光束。每道光束会摧毁其路径上的前 $R$ 个舱室。如果其他舱室位于被摧毁舱室的上方，这些舱室会向下掉落。

在 $K$ 次射击后，决定对飞船进行空袭。选择一个大小为 $P \times P$ 的区域，该区域包含最多数量的剩余舱室，以将它们全部摧毁，这是很有意义的。

编写一个程序，计算通过对大小为 $P \times P$ 的区域进行空袭所能摧毁的剩余舱室的最大数量。

输入格式

第一行包含 5 个整数 $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$ 列的整数表示飞船对应部分（如右图所示）的舱室数量。每个整数都在 $1 \dots 10^6$ 范围内。

接下来的 $K$ 行描述激光射击。每行包含一个字符和 2 个整数。

字符定义了被射击的飞船侧面：W（西）、E（东）、S（南）、N（北）。

如果是西（W）或东（E），第一个整数定义行号；如果是北（N）或南（S），第一个整数定义列号。第二个整数表示被射击的水平层数（高度）。

行和列的编号与输入中相同，层数从 1 开始编号。每个整数都在 $1 \dots 10^6$ 范围内。

输出格式

你需要输出在 $K$ 次激光射击后，包含在某个大小为 $P \times P$ 的区域内的剩余舱室的最大数量。

样例

输入样例 1

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

输出样例 1

6

说明

在第二张图片中，你可以看到第一张图片中的飞船在样例输入中描述的射击后的状态，以及包含最多剩余舱室的 $2 \times 2$ 区域之一。