#include <queue>
#include <bitset>
#include <fstream>

using namespace std;

class InputReader
{
public:
    static const int BUFF_SIZE = 1 << 17;
    FILE *fin;
    int bp;
    char buff[BUFF_SIZE];
    InputReader (const char *file_name)
    {
        fin = fopen(file_name, "r");
        bp = BUFF_SIZE - 1;
    }
    void adv()
    {
        if (++bp == BUFF_SIZE)
        {
            fread(buff, sizeof(char), BUFF_SIZE, fin);
            bp = 0;
        }
    }
    InputReader& operator >> (int& num)
    {
        num = 0;
        while (isdigit(buff[bp]) == false)
            adv();
        while (isdigit(buff[bp]))
        {
            num = num * 10 + buff[bp] - '0';
            adv();
        }
        return *this;
    }
};

InputReader fin("sahara.in");
ofstream fout("sahara.out");

const int MAXN = 1005;

int mat[MAXN][MAXN];
int n, m, a, q;

int di[] = {0, 0, -1, 1};
int dj[] = {-1, 1, 0, 0};

queue < pair < int, int > > Q;
bitset < MAXN > um[MAXN];

inline bool valid(int i, int j)
{
    return (i >= 1 && i <= n && j >= 1 && j <= m && !um[i][j]);
}

void ump(int A, int B)
{
    Q.push(make_pair(A, B));
    while (!Q.empty())
    {
        int i = Q.front().first;
        int j = Q.front().second;
        Q.pop();
        for (int k = 0; k < 4; ++k)
        {
            int inou = i + di[k];
            int jnou = j + dj[k];
            if (valid(inou, jnou) && mat[inou][jnou] >= q)
            {
                ++a;
                um[inou][jnou] = 1;
                Q.push(make_pair(inou, jnou));
            }
        }
    }
}

int main()
{
    int t, l1, l2, c1, c2, x, i, j, amax = 0;
    fin >> n >> m >> q >> t;
    while (t--)
    {
        fin >> l1 >> c1 >> l2 >> c2 >> x;
        mat[l1][c1] += x;
        mat[l2 + 1][c2 + 1] += x;
        mat[l2 + 1][c1] -= x;
        mat[l1][c2 + 1] -= x;
    }
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= m; ++j)
        {
            mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
        }
    }
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= m; ++j)
        {
            if (!um[i][j] && mat[i][j] >= q)
            {
                a = 0;
                ump(i, j);
                if (a > amax) amax = a;
            }
        }
    }
    fout << amax << '\n';
    return 0;
}