TASK НЛО

/*
ID: wtfalex2
LANG: C++14
PROB: castle
*/
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:256000000")

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <ctime>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <deque>
#include <cassert>
#include <cstdlib>
#include <bitset>
#include <algorithm>
#include <string>
#include <list>
#include <fstream>
#include <cstring>
#include <climits>
#include <stack>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<string, int> psi;
typedef vector<string> vs;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<pii> vpii;
typedef vector<pair<ll, ll> > vpll;
typedef long double ld;

#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define for1(i, n) for (int i = 1; i <= (int)n; i++)
#define forq(i, s, t) for (int i = s; i <= t; i++)
#define ford(i, s, t) for (int i = s; i >= t; i--)
#define mk make_pair
#define inb push_back
#define outb pop_back
#define all(v) v.begin(), v.end()
#define X first
#define Y second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sqr(x) (x) * (x)
#define y1 amdknkgsdaasdwapgnpikn
//
#define mp make_pair
#define pb push_back
#define XX first
#define YY second
//

const ld EPS = 1e-9;
const ld pi = acos(-1.0);

const int MAXN = (int)4e5 + 7;
const ll INF = (ll)(1ll << 31ll) - 1ll;
const ll LINF = (ll)7e18;
const ll MOD = (ll)1e9 + 7;
const int CHASH = (ll)239017;
const ld DINF = (ld)1000000000000000.0;

void mkfile();
int solve();

int main()
{
#define TASK "ufo"
#ifdef _DEBUG
    mkfile();
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("test.txt", "w", stderr);
    ld tstart = TIME;
    srand(2299);
#else
    freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
    //freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout), freopen("test.txt", "w", stderr);
    srand(time(0));
#endif
    solve();
#ifdef _DEBUG
    ld tend = TIME;
    cerr << tend - tstart << " s.\n";
#endif
    return 0;
}

void mkfile()
{
    freopen("input.txt", "a+", stdout);
    srand(time(0));
    return;
}

bool equal(double a, double b)
{
    return abs(a - b) < EPS;
}

const int MM = (int)4e8 + 7;

int n, m, p, r, k;
int a[1000007];
int t[2][4000007];
int ans;

void buildRow(int id, int v, int tl, int tr)
{
    if (tl == tr)
        t[0][((id * m) << 2) + v] = a[id * m + tl];
    else
    {
        int tm = tl + tr >> 1;
        buildRow(id, (v << 1) + 1, tl, tm);
        buildRow(id, (v << 1) + 2, tm + 1, tr);
        t[0][((id * m) << 2) + v] = max(t[0][((id * m) << 2) + (v << 1) + 1], t[0][((id * m) << 2) + (v << 1) + 2]);
    }
}

void buildCol(int id, int v, int tl, int tr)
{
    if (tl == tr)
        t[1][v * m + id] = a[tl * m + id];
    else
    {
        int tm = tl + tr >> 1;
        buildCol(id, (v << 1) + 1, tl, tm);
        buildCol(id, (v << 1) + 2, tm + 1, tr);
        t[1][v * m + id] = max(t[1][((v << 1) + 1) * m + id], t[1][((v << 1) + 2) * m + id]);
    }
}

int findLRow(int id, int v, int tl, int tr, int pos, int val)
{
    if (tr < pos || t[0][((id * m) << 2) + v] < val)
        return -1;
    if (tl == tr)
        return tl;
    int tm = tl + tr >> 1;
    int ql = -1;
    if (!(tr < pos || t[0][((id * m) << 2) + (v << 1) + 1] < val))
        ql = findLRow(id, (v << 1) + 1, tl, tm, pos, val);
    if (ql == -1)
    {
        if (!(tr < pos || t[0][((id * m) << 2) + (v << 1) + 2] < val))
            return findLRow(id, (v << 1) + 2, tm + 1, tr, pos, val);
        return -1;
    }
    return ql;
}

int findRRow(int id, int v, int tl, int tr, int pos, int val)
{
    if (tl > pos || t[0][((id * m) << 2) + v] < val)
        return -1;
    if (tl == tr)
        return tl;
    int tm = tl + tr >> 1;
    int qr = -1;
    if (!(tl > pos || t[0][((id * m) << 2) + (v << 1) + 2] < val))
        qr = findRRow(id, (v << 1) + 2, tm + 1, tr, pos, val);
    if (qr == -1)
    {
        if (!(tl > pos || t[0][((id * m) << 2) + (v << 1) + 1] < val))
            return findRRow(id, (v << 1) + 1, tl, tm, pos, val);
        return -1;
    }
    return qr;
}

int findUCol(int id, int v, int tl, int tr, int pos, int val)
{
    if (tr < pos || t[1][v * m + id] < val)
        return -1;
    if (tl == tr)
        return tl;
    int tm = tl + tr >> 1;
    int ql = -1;
    if (!(tr < pos || t[1][((v << 1) + 1) * m + id] < val))
        ql = findUCol(id, (v << 1) + 1, tl, tm, pos, val);
    if (ql == -1)
    {
        if (!(tr < pos || t[1][((v << 1) + 2) * m + id] < val))
            return findUCol(id, (v << 1) + 2, tm + 1, tr, pos, val);
        return -1;
    }
    return ql;
}

int findDCol(int id, int v, int tl, int tr, int pos, int val)
{
    if (tl > pos || t[1][v * m + id] < val)
        return -1;
    if (tl == tr)
        return tl;
    int tm = tl + tr >> 1;
    int qr = -1;
    if (!(tl > pos || t[1][((v << 1) + 2) * m + id] < val))
        qr = findDCol(id, (v << 1) + 2, tm + 1, tr, pos, val);
    if (qr == -1)
    {
        if (!(tl > pos || t[1][((v << 1) + 1) * m + id] < val))
            return findDCol(id, (v << 1) + 1, tl, tm, pos, val);
        return -1;
    }
    return qr;
}

void updateRow(int id, int v, int tl, int tr, int pos)
{
    if (tl == tr)
    {
        --t[0][((id * m) << 2) + v];
        return;
    }
    int tm = tl + tr >> 1;
    if (!(tl > pos || tm < pos))
        updateRow(id, (v << 1) + 1, tl, tm, pos);
    if (!(tm + 1 > pos || tr < pos))
        updateRow(id, (v << 1) + 2, tm + 1, tr, pos);
    t[0][((id * m) << 2) + v] = max(t[0][((id * m) << 2) + (v << 1) + 1], t[0][((id * m) << 2) + (v << 1) + 2]);
}

void updateCol(int id, int v, int tl, int tr, int pos)
{
    if (tl == tr)
    {
        --t[1][v * m + id];
        return;
    }
    int tm = tl + tr >> 1;
    if (!(tl > pos || tm < pos))
        updateCol(id, (v << 1) + 1, tl, tm, pos);
    if (!(tm + 1 > pos || tr < pos))
        updateCol(id, (v << 1) + 2, tm + 1, tr, pos);
    t[1][v * m + id] = max(t[1][((v << 1) + 1) * m + id], t[1][((v << 1) + 2) * m + id]);
}

void getRow(int id, int v, int tl, int tr)
{
    if (tl == tr)
        a[id * m + tl] = t[0][((id * m) << 2) + v];
    else
    {
        int tm = tl + tr >> 1;
        getRow(id, (v << 1) + 1, tl, tm);
        getRow(id, (v << 1) + 2, tm + 1, tr);
    }
}

int solve()
{
    scanf("%d %d %d %d %d", &n, &m, &r, &k, &p);
    forn(i, n)
        forn(j, m)
            scanf("%d", &a[i * m + j]);
    forn(i, n)
        buildRow(i, 0, 0, m - 1);
    forn(i, m)
        buildCol(i, 0, 0, n - 1);
    forn(it, k)
    {
        char c;
        int x, h;
        scanf(" %c %d %d", &c, &x, &h);
        --x;
        if (c == 'N')
        {
            int i = 0;
            int pos = -2;
            while (i < r && pos != -1)
            {
                pos = findUCol(x, 0, 0, n - 1, pos + 1, h);
                if (pos != -1)
                {
                    updateCol(x, 0, 0, n - 1, pos);
                    updateRow(pos, 0, 0, m - 1, x);
                }
                ++i;
            }
        }
        if (c == 'S')
        {
            int i = 0;
            int pos = n;
            while (i < r && pos != -1)
            {
                pos = findDCol(x, 0, 0, n - 1, pos - 1, h);
                if (pos != -1)
                {
                    updateCol(x, 0, 0, n - 1, pos);
                    updateRow(pos, 0, 0, m - 1, x);
                }
                ++i;
            }
        }
        if (c == 'W')
        {
            int i = 0;
            int pos = -2;
            while (i < r && pos != -1)
            {
                pos = findLRow(x, 0, 0, m - 1, pos + 1, h);
                if (pos != -1)
                {
                    updateRow(x, 0, 0, m - 1, pos);
                    updateCol(pos, 0, 0, n - 1, x);
                }
                ++i;
            }
        }
        if (c == 'E')
        {
            int i = 0;
            int pos = m;
            while (i < r && pos != -1)
            {
                pos = findRRow(x, 0, 0, m - 1, pos - 1, h);
                if (pos != -1)
                {
                    updateRow(x, 0, 0, m - 1, pos);
                    updateCol(pos, 0, 0, n - 1, x);
                }
                ++i;
            }
        }
    }
    forn(i, n)
        getRow(i, 0, 0, m - 1);
    forn(i, n)
    {
        forn(j, m)
        {
            if (i && j)
                a[i * m + j] = ((a[i * m + j] + a[(i - 1) * m + j] + a[i * m + j - 1] - a[(i - 1) * m + j - 1]) % MM) + MM % MM;
            if (i && !j)
                a[i * m + j] = (a[i * m + j] + a[(i - 1) * m + j]) % MM;
            if (!i && j)
                a[i * m + j] = (a[i * m + j] + a[i * m + j - 1]) % MM;
            if (i >= p && j >= p)
                ans = max(ans, (((a[i * m + j] + a[(i - p) * m + j - p]) % MM - (a[(i - p) * m + j] + a[i * m + j - p]) % MM) % MM + MM) % MM);
            if (i >= p && j == p - 1)
                ans = max(ans, ((a[i * m + j] - a[(i - p) * m + j]) % MM + MM) % MM);
            if (i == p - 1 && j >= p)
                ans = max(ans, ((a[i * m + j] - a[i * m + j - p]) % MM + MM) % MM);
            if (i == p - 1 && j == p - 1)
                ans = max(ans, a[i * m + j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}