UFO

Snakeland's security service damaged a hostile alien ship and forced it to land. The ship is built from unit cubes called compartments. Seen from above it covers a grid of $N$ rows and $M$ columns, and over the cell in row $i$, column $j$ there is a stack of $h_{i,j}$ compartments. Layers are numbered from 1 at the ground, so the cell in row $i$, column $j$ holds a compartment on layer $L$ exactly when $h_{i,j} \ge L$.

The compartments are made of a metal that only a laser cuts. Laser devices stand on all four sides of the ship, and each device fires beams perpendicular to its own side. A beam runs horizontally along one row or one column at one fixed layer.

Row 1 is the northmost row and column 1 is the westmost column. A beam fired from the west travels along its row from column 1 towards column $M$, and a beam fired from the east travels from column $M$ towards column 1. A beam fired from the north travels along its column from row 1 towards row $N$, and a beam fired from the south travels from row $N$ towards row 1.

A beam destroys the first $R$ compartments on its path. Looking at one cell at a time in the direction of travel, the beam destroys the compartment on the layer being shot whenever that cell's stack still reaches the layer, and it stops once it has destroyed $R$ of them. The compartments above a destroyed one drop by one layer, so destroying a compartment in a cell lowers that cell's stack by 1. When the beam leaves the ship before destroying $R$ compartments, it destroys fewer.

After $K$ shots the ship is bombed from the air. The bomb covers a grid-aligned square of $P$ rows and $P$ columns and destroys every compartment left over those $P \times P$ cells. Write a program that computes the largest number of compartments one bomb can destroy.

The first line contains five integers $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)$).

Each of the next $N$ lines contains $M$ integers. The $j$-th integer on the $i$-th of these lines is $h_{i,j}$, the number of compartments stacked over the cell in row $i$, column $j$ ($1 \le h_{i,j} \le 10^6$).

Each of the next $K$ lines describes one shot with a letter and two integers. The letter is the side the beam comes from and is one of W, E, S, N. For W and E the first integer is a row number between 1 and $N$; for N and S it is a column number between 1 and $M$. The second integer is the layer being shot, between 1 and $10^6$. The shots are processed in the order given.

Print one integer, the largest number of compartments left over any $P \times P$ block of cells after all $K$ shots.