#include <bits/stdc++.h>
using namespace std;
struct Segtree {
vector<int> ladd, sgt;
Segtree(int N) {
ladd.resize(N<<2, 0);
sgt.resize(N<<2, 0);
}
void push(int i) {
if (!ladd[i]) return;
ladd[i<<1] += ladd[i];
ladd[i<<1|1] += ladd[i];
sgt[i<<1] += ladd[i];
sgt[i<<1|1] += ladd[i];
ladd[i] = 0;
}
void radd(int ql, int qr, int v, int i = 1, int tl = 0, int tr = -1) {
if (tr < 0) tr += sgt.size() >> 2;
if (tl > qr || tr < ql) return;
if (ql <= tl && tr <= qr) {
sgt[i] += v, ladd[i] += v;
} else {
push(i);
int mid = tl + tr >> 1;
radd(ql, qr, v, i<<1, tl, mid);
radd(ql, qr, v, i<<1|1, mid+1, tr);
sgt[i] = min(sgt[i<<1], sgt[i<<1|1]);
}
}
int qry(int ql, int qr, int i = 1, int tl = 0, int tr = -1) {
if (tr < 0) tr += sgt.size() >> 2;
if (tl > qr || tr < ql) return INT_MAX;
if (ql <= tl && tr <= qr) return sgt[i];
push(i);
int mid = tl + tr >> 1;
return min(qry(ql, qr, i<<1, tl, mid), qry(ql, qr, i<<1|1, mid+1, tr));
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, B, P;
cin >> N >> M >> B >> P;
vector<vector<int>> A(P, vector<int>(5));
for (auto &v : A) {
for (int &i : v) {
cin >> i, i--;
}
v[4]++;
}
if (1) {
int lo = 0, hi = min(N, M);
while (lo < hi) {
int mid = lo + hi + 1 >> 1;
vector<vector<int>> evs;
for (auto &v : A) {
evs.push_back({v[0], max(0, v[1]-mid+1), min(M-mid, v[3]), v[4]});
if (v[2] + mid < N) {
evs.push_back({v[2] + mid, max(0, v[1]-mid+1), min(M-mid, v[3]), -v[4]});
}
}
sort(evs.begin(), evs.end());
Segtree sgt(M-mid+1);
bool can = false;
for (int i = mid-1, j = 0; i < N; i++) {
for (; j < evs.size() && evs[j][0] <= i; j++) {
sgt.radd(evs[j][1], evs[j][2], evs[j][3]);
}
can |= sgt.qry(0, M-mid) <= B;
}
can ? lo = mid : hi = mid - 1;
}
cout << lo << '\n';
}
}
