#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N_ (1 << 20) /* N_ = pow2(ceil(log2(M))) */
#define M 1000000
#define N 400000
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int *yy;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (yy[ii[j]] == yy[i_])
j++;
else if (yy[ii[j]] < yy[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int xx1[N], xx2[N], yy1[N], yy2[N], ii1[N], ii2[N], cc[N], n, x_, y_, c, s;
int st[N_ * 2], lz[N_ * 2]; char ok[N_ * 2];
void update(int l, int r, int x) {
int l_ = l += N_, r_ = r += N_;
if (l > r)
return;
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
st[l] += x, lz[l] += x, l++;
if ((r & 1) == 0)
st[r] += x, lz[r] += x, r--;
}
while (l_ > 1)
l_ >>= 1, st[l_] = min(st[l_ << 1 | 0], st[l_ << 1 | 1]) + lz[l_];
while (r_ > 1)
r_ >>= 1, st[r_] = min(st[r_ << 1 | 0], st[r_ << 1 | 1]) + lz[r_];
}
int h1, h2;
int try(int y) {
int i;
while (h1 < n && yy1[i = ii1[h1]] - s + 1 <= y)
h1++, update(max(xx1[i] - s + 1, 0), min(xx2[i], x_ - s), cc[i]);
while (h2 < n && yy2[i = ii2[h2]] + 1 <= y)
h2++, update(max(xx1[i] - s + 1, 0), min(xx2[i], x_ - s), -cc[i]);
return st[1] <= c;
}
int check() {
int y;
memset(st, 0, N_ * 2 * sizeof *st), memset(lz, 0, N_ * 2 * sizeof *lz);
update(x_ - s + 1, N_ - 1, c + 1);
h1 = 0, h2 = 0;
if (try(0))
return 1;
while (h1 < n || h2 < n) {
if (h1 == n)
y = yy2[ii2[h2]] + 1;
else if (h2 == n)
y = yy1[ii1[h1]] - s + 1;
else
y = min(yy1[ii1[h1]] - s + 1, yy2[ii2[h2]] + 1);
if (y + s - 1 >= y_)
break;
if (try(y))
return 1;
}
return 0;
}
int main() {
int i, lower, upper;
scanf("%d%d%d%d", &x_, &y_, &c, &n);
for (i = 0; i < n; i++) {
int x1, y1, x2, y2, c;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c), x1--, x2--, y1--, y2--;
xx1[i] = x1, xx2[i] = x2, yy1[i] = y1, yy2[i] = y2, cc[i] = c;
ii1[i] = ii2[i] = i;
}
yy = yy1, sort(ii1, 0, n);
yy = yy2, sort(ii2, 0, n);
lower = 0, upper = (x_ < y_ ? x_ : y_) + 1;
while (upper - lower > 1) {
s = (lower + upper) / 2;
if (check())
lower = s;
else
upper = s;
}
printf("%d\n", lower);
return 0;
}
