#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
const int SEG_N = 1 << 19;
long long node[2 * SEG_N];
long long lazy[SEG_N];
void build(int sz) {
for (int i = 0; i < 2 * SEG_N; i++) {
node[i] = 1LL << 60;
}
for (int i = 0; i < SEG_N; i++) {
lazy[i] = 0;
}
for (int i = 0; i < sz; i++) {
node[i + SEG_N] = 0;
}
for (int i = SEG_N - 1; i > 0; i--) {
node[i] = min(node[i * 2], node[i * 2 + 1]);
}
}
void eval(int k) {
node[2 * k] = lazy[k] + node[2 * k];
node[2 * k + 1] = lazy[k] + node[2 * k + 1];
if (2 * k < SEG_N) {
lazy[2 * k] = lazy[k] + lazy[2 * k];
lazy[2 * k + 1] = lazy[k] + lazy[2 * k + 1];
}
lazy[k] = 0;
}
void update(int x, int y, long long v, int k = 1, int l = 0, int r = SEG_N) {
if (y <= l || r <= x) {
return;
}
if (x <= l && r <= y) {
node[k] = v + node[k];
if (k < SEG_N) {
lazy[k] = v + lazy[k];
}
} else {
eval(k);
update(x, y, v, 2 * k, l, (l + r) / 2);
update(x, y, v, 2 * k + 1, (l + r) / 2, r);
node[k] = min(node[2 * k], node[2 * k + 1]);
}
}
const int N = (int) 1e6 + 10;
const int P = (int) 4e5 + 10;
tuple<int, int, int, int> a[P];
tuple<int, int, int, int> b[P];
int mp[N];
int xs[2 * P];
int ys[4 * P];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int h, w;
cin >> h >> w;
int d;
cin >> d;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
x1--, y1--;
a[i] = make_tuple(x1, y1, y2, c);
b[i] = make_tuple(x2, y1, y2, c);
}
sort(a, a + n);
sort(b, b + n);
int hi = min(w, h) + 1;
int lo = 0;
while (hi - lo > 1) {
int mid = (hi + lo) / 2;
int aid = 0;
int bid = 0;
int ok = 0;
for (int i = 0; i < n; i++) {
auto [x2, y1, y2, c] = b[i];
y1 = max(0, y1 - mid + 1);
y2 = min(w - mid + 1, y2);
ys[2 * i] = y1;
ys[2 * i + 1] = y2;
xs[i] = min(h - mid, x2);
}
for (int i = 0; i < n; i++) {
auto [x1, y1, y2, c] = a[i];
y1 = max(0, y1 - mid + 1);
y2 = min(w - mid + 1, y2);
ys[2 * n + 2 * i] = y1;
ys[2 * n + 2 * i + 1] = y2;
xs[i + n] = max(0, x1 - mid + 1);
}
xs[2 * n] = 0;
xs[2 * n + 1] = h - mid;
sort(xs, xs + 2 * n + 2);
int xsz = (int) (unique(xs, xs + 2 * n + 2) - xs);
ys[4 * n] = 0;
ys[4 * n + 1] = w - mid + 1;
sort(ys, ys + 4 * n + 2);
int ysz = (int) (unique(ys, ys + 4 * n + 2) - ys);
for (int i = 0; i < ysz; i++) {
mp[ys[i]] = i;
}
build(ysz - 1);
for (int xid = 0; xid < xsz; xid++) {
int i = xs[xid];
while (bid < n && get<0>(b[bid]) <= i) {
auto [x2, y1, y2, c] = b[bid];
y1 = max(0, y1 - mid + 1);
y2 = min(w - mid + 1, y2);
y1 = mp[y1];
y2 = mp[y2];
update(y1, y2, -c);
bid++;
}
while (aid < n && get<0>(a[aid]) - mid + 1 <= i) {
auto [x1, y1, y2, c] = a[aid];
y1 = max(0, y1 - mid + 1);
y2 = min(w - mid + 1, y2);
y1 = mp[y1];
y2 = mp[y2];
update(y1, y2, c);
aid++;
}
if (node[1] <= d) {
ok = 1;
break;
}
}
if (ok) {
lo = mid;
} else {
hi = mid;
}
}
cout << lo << '\n';
return 0;
}
