#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000100
#define MAXP 400400
struct Node {
int mn, sum;
Node(int v) : mn(v), sum(v) {}
Node() : Node(0) {}
Node operator+(const Node &nd) {
Node ans;
ans.mn=min(mn, sum+nd.mn);
ans.sum=this->sum+nd.sum;
return ans;
}
};
Node seg[4*MAXN];
int xx1[MAXP], yy1[MAXP], xx2[MAXP], yy2[MAXP];
int c[MAXP];
vector<pair<pair<int, int>, pair<int, int>>> vc1;
vector<pair<pair<int, int>, pair<int, int>>> vc2;
int m, n, p, b;
#define MP make_pair
int nid[MAXN];
void build(int n, int l, int r) {
seg[n]=Node();
if(l==r) nid[l]=n;
else {
int mid=(l+r)/2;
build(2*n, l, mid);
build(2*n+1, mid+1, r);
}
}
void build() {
build(1, 1, n);
}
void update(int i, int v) {
if(i>n) return;
int nd=nid[i];
seg[nd]=Node(seg[nd].mn+v);
while(nd>1) {
int nn=nd/2;
if(nd&1) {
seg[nn]=seg[nd-1]+seg[nd];
} else {
seg[nn]=seg[nd]+seg[nd+1];
}
nd=nn;
}
}
int test(int l) {
vector<pair<pair<int, int>, pair<int, int>>> v1;
vector<pair<pair<int, int>, pair<int, int>>> v2;
n-=l-1;
m-=l-1;
build();
for(auto pr : vc1) {
v1.push_back(MP(MP(max(pr.first.first-l+1, 1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
}
for(auto pr : vc2) {
v2.push_back(MP(MP(min(pr.first.first, m+1), pr.first.second), MP(max(pr.second.first-l+1, 1), min(pr.second.second, n+1))));
}
vector<pair<pair<int, int>, pair<int, int>>> vec(2*p);
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vec.begin());
int lst=1;
for(auto pr : vec) {
if(pr.first.first!=lst) {
if(seg[1].mn<=b) {
n+=l-1;
m+=l-1;
return 1;
}
lst=pr.first.first;
}
update(pr.second.first, pr.first.second);
update(pr.second.second, -pr.first.second);
}
int ans=lst<=m;
n+=l-1;
m+=l-1;
return ans;
}
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> m >> n >> b >> p;
for(int i=0;i<p;i++) cin >> xx1[i] >> yy1[i] >> xx2[i] >> yy2[i] >> c[i];
if(!b) {
for(int i=0;i<p;i++) c[i]=1;
}
for(int i=0;i<p;i++) vc1.push_back(MP(MP(xx1[i], c[i]), MP(yy1[i], yy2[i]+1)));
for(int i=0;i<p;i++) vc2.push_back(MP(MP(xx2[i]+1, -c[i]), MP(yy1[i], yy2[i]+1)));
sort(vc1.begin(), vc1.end());
sort(vc2.begin(), vc2.end());
int l=0, r=min(m, n);
while(l<r) {
int mid=(l+r+1)/2;
if(test(mid)) l=mid;
else r=mid-1;
}
cout << l << endl;
}
