#include <bits/stdc++.h>
using namespace std;
int n, m, k, r, p;
vector<vector<int>>aint_lin, aint_col, a;
vector<vector<long long>>sum;
void init () {
aint_lin.resize(n + 2);
aint_col.resize(m + 2);
a.resize(n+2);
sum.resize(n+2);
for (int i = 0; i <= n + 1; i++) {
a[i].resize(m + 2);
sum[i].resize(m + 2);
aint_lin[i].resize(4 * m + 2);
}
for (int i = 0; i <= m + 1; i++)
aint_col[i].resize(4 * n + 2);
}
void updateLin (int poz, int nod, int st, int dr, int pozhatz, int val) {
if (st == dr) {
aint_lin[poz][nod] = val;
return;
}
int mid = (st + dr) / 2;
if (pozhatz <= mid)
updateLin(poz, 2 * nod, st, mid, pozhatz, val);
else
updateLin(poz, 2 * nod + 1, mid + 1, dr, pozhatz, val);
aint_lin[poz][nod] = max(aint_lin[poz][2 * nod], aint_lin[poz][2 * nod + 1]);
}
void updateCol (int poz, int nod, int st, int dr, int pozhatz, int val) {
if (st == dr) {
aint_col[poz][nod] = val;
return;
}
int mid = (st + dr) / 2;
if (pozhatz <= mid)
updateCol(poz, 2 * nod, st, mid, pozhatz, val);
else
updateCol(poz, 2 * nod + 1, mid + 1, dr, pozhatz, val);
aint_col[poz][nod] = max(aint_col[poz][2 * nod], aint_col[poz][2 * nod + 1]);
}
int queryLin (bool ok, int nod, int st, int dr, int poz, int lvl) {
if (st == dr)
return st;
int mid = (st + dr) / 2;
if (!ok) {
if (aint_lin[poz][2 * nod] >= lvl)
return queryLin(ok, 2* nod, st, mid, poz, lvl);
else
return queryLin(ok, 2 * nod + 1, mid + 1, dr, poz, lvl);
}
else {
if (aint_lin[poz][2 * nod + 1] >= lvl)
return queryLin(ok, 2* nod + 1, mid + 1, dr, poz, lvl);
else
return queryLin(ok, 2 * nod, st, mid, poz, lvl);
}
}
int queryCol (bool ok, int nod, int st, int dr, int poz, int lvl) {
if (st == dr)
return st;
int mid = (st + dr) / 2;
if (!ok) {
if (aint_col[poz][2 * nod] >= lvl)
return queryCol(ok, 2* nod, st, mid, poz, lvl);
else
return queryCol(ok, 2 * nod + 1, mid + 1, dr, poz, lvl);
}
else {
if (aint_col[poz][2 * nod + 1] >= lvl)
return queryCol(ok, 2* nod + 1, mid + 1, dr, poz, lvl);
else
return queryCol(ok, 2 * nod, st, mid, poz, lvl);
}
}
void Laserlin (int dr, bool ok, int poz, int lvl) {
int r1 = r;
int last = 0;
vector<int > kasa;
while (r1 && aint_lin[poz][1] >= lvl) {
int x = queryLin(ok, 1, 1 , dr, poz, lvl);
a[poz][x]--;
kasa.push_back(x);
last = x;
updateLin(poz, 1, 1, m, x, 0);
r1--;
}
for (auto it : kasa) {
updateLin(poz, 1, 1, m, it, a[poz][it]);
updateCol(it, 1, 1, n, poz, a[poz][it]);
}
}
void Lasercol (int dr, bool ok, int poz, int lvl) {
int r1 = r;
int last = 0;
vector<int > kasa;
while (r1 && aint_col[poz][1] >= lvl) {
int x = queryCol(ok, 1, 1, dr, poz, lvl);
a[x][poz]--;
kasa.push_back(x);
last = x;
updateCol(poz, 1, 1, n, x, 0);
r1--;
}
for (auto it : kasa) {
updateLin(it, 1, 1, m, poz, a[it][poz]);
updateCol(poz, 1, 1, n, it, a[it][poz]);
}
}
int main()
{
cin >> n >> m >> r >> k >> p;
init();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
updateLin(i, 1, 1, m, j, a[i][j]);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
updateCol(i, 1, 1, n, j, a[j][i]);
char ch;
int poz, lvl;
for (int i = 1; i <= k; i++) {
cin >> ch >> poz >> lvl;
if (ch == 'N') Lasercol(n, 0, poz, lvl);
if (ch == 'S') Lasercol(n, 1, poz, lvl);
if (ch == 'W') Laserlin(m, 0, poz, lvl);
if (ch == 'E') Laserlin(m, 1, poz, lvl);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
long long ans = 0;
for (int i = p; i <= n; i++)
for (int j = p; j <= m; j++)
ans = max(ans, sum[i][j] - sum[i - p][j] - sum[i][j - p] + sum[i - p][j - p]);
cout << ans;
return 0;
}
