UFO

An alien spaceship has been forced down in a desert and has to be destroyed. The ship is built from unit cube blocks, and its bottom layer is an $N \times M$ rectangle. Cell $(i, j)$ of that rectangle carries a stack of blocks, and the layers of a stack are numbered $1$, $2$ and so on from the ground up. Rows are numbered $1$ to $N$ from the north side to the south side, and columns are numbered $1$ to $M$ from the west side to the east side. The figure shows the top view of a ship with $N = 4$ and $M = 8$.

The blocks are made of a metal that only a laser can cut, so laser guns were placed on the four sides of the ship. A ray flies perpendicular to the side it was fired from, parallel to the ground, along one fixed layer.

A shot is given by a side, an index, and a height $h$. A ray fired from the west runs along the given row from column $1$ toward column $M$, and a ray fired from the east runs along the same row from column $M$ toward column $1$. A ray fired from the north runs along the given column from row $1$ toward row $N$, and a ray fired from the south runs along the same column from row $N$ toward row $1$.

The ray passes over the cells of that line one at a time. If a cell holds at least $h$ blocks, the ray destroys the block on layer $h$, every block above it drops one layer, and the height of that cell falls by $1$. At most one block is destroyed in a cell, and the ray moves straight on to the next one. A cell holding fewer than $h$ blocks lets the ray through unchanged. The ray stops once it has destroyed $R$ blocks, and it also stops if it leaves the ship before that.

After the $K$ shots an airstrike is called on a square area of size $P \times P$. The area with the largest number of surviving blocks is chosen, and the strike destroys every block inside it. Compute how many blocks the airstrike destroys.

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 number on the $i$-th line is the number of blocks stacked on cell $(i, j)$, between $1$ and $10^6$.

Each of the next $K$ lines describes one shot with a single character and two integers, separated by spaces. The character is W for west, E for east, S for south, or N for north. 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 height of the shot, between $1$ and $10^6$.

Print one integer, the largest number of blocks left inside a $P \times P$ area after all $K$ shots.

The figure shows the ship of the first example after every shot of that example. The shaded square is the $2 \times 2$ area holding the most blocks.