#include <bits/stdc++.h>
using namespace std;
char buf[1 << 17];
int idx, nidx;
static inline char read() {
if (idx == nidx) {
nidx = fread(buf, 1, 1 << 17, stdin);
idx = 0;
}
return buf[idx++];
}
static inline int readInt() {
int sum = 0;
bool flag = false;
char now = read();
while (now == ' ' || now == '\n')
now = read();
if (now == '-') {
flag = true;
now = read();
}
while (now != ' '&&now != '\n') {
sum *= 10;
sum += now - '0';
now = read();
}
if (flag)
return -sum;
return sum;
}
int tree[1 << 21][2];
void update(int le, int ri, int val, int nodele, int noderi, int node) {
if (le > noderi || ri < nodele)return;
if (le <= nodele && noderi <= ri) {
tree[node][0] += val;
tree[node][1] += val;
return;
}
int mid = (nodele + noderi) / 2;
update(le, ri, val, nodele, mid, node * 2);
update(le, ri, val, mid + 1, noderi, node * 2 + 1);
tree[node][0] = min(tree[node * 2][0], tree[node * 2 + 1][0]) + tree[node][1];
}
void init(int nodele, int noderi, int node) {
tree[node][0] = tree[node][1] = 0;
if (nodele == noderi) return;
int mid = (nodele + noderi) / 2;
init(nodele, mid, node * 2);
init(mid + 1, noderi, node * 2 + 1);
}
int n, m, b, p;
vector<pair<pair<int,int>,int> > in[1000005], out[1000005];
bool possi(int k) {
init(1, m - k + 1, 1);
for (int i = 1; i <= n; i++) {
for (auto &v : in[i]) update(max(1, v.first.first - k + 1), min(m - k + 1, v.first.second), v.second, 1, m - k + 1, 1);
if (i >= k) for (auto &v : out[i - k]) update(max(1, v.first.first - k + 1), min(m - k + 1, v.first.second), v.second, 1, m - k + 1, 1);
if (i >= k && tree[1][0] <= b) return true;
}
return false;
}
int main() {
//scanf("%d%d%d%d", &n, &m, &b, &p);
n = readInt();
m = readInt();
b = readInt();
p = readInt();
for (int i = 0; i < p; i++) {
int x1, y1, x2, y2, c;
//scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
x1 = readInt();
y1 = readInt();
x2 = readInt();
y2 = readInt();
c = readInt();
in[x1].push_back({ {y1, y2}, b ? c : 1 });
out[x2].push_back({ {y1, y2}, b ? -c : -1 });
}
int le, ri, ans, mid;
le = 1;
ri = min(n,m);
ans = 0;
while (le <= ri) {
mid = (le + ri) / 2;
if (possi(mid)) {
ans = mid;
le = mid + 1;
}
else ri = mid - 1;
}
printf("%d\n", ans);
return 0;
}
