#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Seg{
int tree[2202000], lazy[2202000];
void init(int i, int l, int r){
tree[i] = lazy[i] = 0;
if (l==r) return;
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
}
void propagate(int i, int l, int r){
tree[i] += lazy[i];
if (l!=r) lazy[i<<1] += lazy[i], lazy[i<<1|1] += lazy[i];
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[i] += x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e, x);
update(i<<1|1, m+1, r, s, e, x);
tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
}tree;
struct Query{
int l, r, c;
Query(){}
Query(int _l, int _r, int _c): l(_l), r(_r), c(_c) {}
};
vector<Query> L[1001000], R[1001000];
int n, m, B;
bool calc(int x){
tree.init(1, 1, m-x+1);
for (int i=1;i<=x;i++){
for (auto &p:L[i]){
tree.update(1, 1, m-x+1, max(1, p.l-x+1), min(m-x+1, p.r), p.c);
//if (x==3) printf("%d: %d %d -> %d %d\n", i, p.l, p.r, max(1, p.l-x+1), min(m-x+1, p.r));
}
}
if (tree.tree[1]<=B) return 1;
for (int i=x+1;i<=n;i++){
for (auto &p:R[i-x]){
tree.update(1, 1, m-x+1, max(1, p.l-x+1), min(m-x+1, p.r), p.c);
}
for (auto &p:L[i]){
tree.update(1, 1, m-x+1, max(1, p.l-x+1), min(m-x+1, p.r), p.c);
}
if (tree.tree[1]<=B) return 1;
}
return 0;
}
int main(){
scanf("%d %d %d", &m, &n, &B);
int q;
scanf("%d", &q);
for (int i=0;i<q;i++){
int x1, y1, x2, y2, c;
scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
if (B==0) c = 1;
L[y1].emplace_back(x1, x2, c);
R[y2].emplace_back(x1, x2, -c);
}
int l = 1, r = min(m, n), ans = 0;
while(l<=r){
int mid = (l+r)>>1;
if (calc(mid)) l = mid+1, ans = mid;
else r = mid-1;
}
//printf("YES\n");
//printf("%d\n", calc(3));
printf("%d\n", ans);
return 0;
}
