#include <bits/stdc++.h>
using namespace std;
const int N = int(1e6) + 10;
int n, m, p;
int budget;
vector <int> x, y, x2, y2, cost;
struct Node {
int pref, suff, mx;
};
Node t[N * 4];
int lazy[N * 4];
struct SegmentTree {
int v;
int tl;
int tr;
SegmentTree(int n) {
v = 1;
tl = 1;
tr = n;
build(v, tl, tr);
};
void add(int l, int r, int incVal) {
update(v, tl, tr, l, r, incVal);
}
int get() {
return t[v].mx;
}
private:
void update(int v, int tl, int tr, int l, int r, int incVal) {
if (l > r) {
return;
}
if (tl == l && tr == r) {
lazy[v] += incVal;
combine(v, tl, tr);
return;
}
int tm = tl + tr >> 1;
update(v << 1, tl, tm, l, min(r, tm), incVal);
update(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, incVal);
combine(v, tl, tr);
}
void build(int v, int tl, int tr) {
if (tl == tr) {
combine(v, tl, tr);
return;
}
int tm = tl + tr >> 1;
build(v << 1, tl, tm);
build(v << 1 | 1, tm + 1, tr);
combine(v, tl, tr);
}
void combine(int v, int tl, int tr) {
if (lazy[v]) {
t[v].mx = 0;
t[v].pref = 0;
t[v].suff = 0;
return;
}
if (tl == tr) {
t[v].mx = 1;
t[v].pref = 1;
t[v].suff = 1;
return;
}
int l = v << 1;
int r = v << 1 | 1;
int tm = tl + tr >> 1;
int szLeft = tm - tl + 1;
int szRight = tr - tm;
t[v].mx = max(t[l].mx, t[r].mx);
if (t[l].pref == szLeft) {
t[v].pref = t[l].pref + t[r].pref;
}
else {
t[v].pref = t[l].pref;
}
if (t[r].suff == szRight) {
t[v].suff = t[l].suff + t[r].suff;
}
else {
t[v].suff = t[r].suff;
}
t[v].mx = max(t[v].mx, t[v].pref);
t[v].mx = max(t[v].mx, t[v].suff);
}
};
vector <int> add[N];
vector <int> del[N];
void solve() {
cin >> n >> m;
cin >> budget;
cin >> p;
x.resize(p);
y.resize(p);
x2.resize(p);
y2.resize(p);
cost.resize(p);
for (int i = 0; i < p; i++) {
cin >> x[i] >> y[i] >> x2[i] >> y2[i] >> cost[i];
}
for (int i = 0; i < p; i++) {
add[x[i]].push_back(i);
del[x2[i] + 1].push_back(i);
}
SegmentTree tree(m + 1);
for (auto i : add[1]) {
tree.add(y[i], y2[i], 1);
}
int r = 1;
int ans = 0;
for (int i = 1; i <= n; i++) {
for (auto i : del[i]) {
tree.add(y[i], y2[i], -1);
}
while (r <= n && tree.get() >= r - i + 1) {
ans = max(ans, r - i + 1);
r++;
for (auto i : add[r]) {
tree.add(y[i], y2[i], 1);
}
}
}
cout << ans << "\n";
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
//freopen("./input.txt", "r", stdin);
solve();
}
