#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;
struct segTree{
struct node{
long long val,laz;
};
node *st;
node def;
int X;
segTree(int n){
int x = ceil(log2(n));
x++;
X=x;
st=new node[(1<<x)];
def.val=0;
def.laz=0;
fill(st,st+(1<<x),def);
}
void push(int ind, int l, int r){
if(st[ind].laz==0)
return;
st[ind].val+=st[ind].laz;
if(l<r){
st[(ind<<1)+1].laz+=st[ind].laz;
st[(ind<<1)+2].laz+=st[ind].laz;
}
st[ind].laz=0;
}
void update(int l, int r,int s, int e, int ind, int val){
push(ind,l,r);
if(e<l||s>r){
return;
}
if(s<=l&&r<=e){
st[ind].laz=val;
push(ind,l,r);
return;
}
int mid = (l+r)>>1;
update(l,mid,s,e,(ind<<1)+1,val);
update(mid+1,r,s,e,(ind<<1)+2,val);
st[ind].val = min(st[(ind<<1)+1].val,st[(ind<<1)+2].val);
}
void rset(){
fill(st,st+(1<<X),def);
}
};
int fin(int len, int m, int n, array<int,4> evs[], int p, segTree &st){
if(len==0){
return 0;
}
len--;
p<<=1;
vector<array<int,3>>evens[m+1];
for(int i = 0;i<p;i++){
array<int,4>e = evs[i];
e[1]-=len;
e[1]=max(0,e[1]);
if(e[3]<0){
e[0]+=len;
}
e[0]=min(e[0],m);
evens[e[0]].push_back({e[1],e[2],e[3]});
}
st.update(0,n-1,0,n-1,0,inf);
evens[len].push_back({0,n-1,-inf});
st.update(0,n-1,n-len,n-1,0,inf);
int ans = inf;
for(int i = 0;i<m;i++){
for(array<int,3>e:evens[i]){
st.update(0,n-1,e[0],e[1],0,e[2]);
}
ans=min(ans,(int)st.st[0].val);
}
st.rset();
return ans;
}
///b=0
struct segTree2{
struct node{
int val,pref,suf,mid,laz,len;
};
node *st;
node def;
void build(int l, int r, int ind){
st[ind].val=0;
st[ind].pref=(r-l+1);
st[ind].suf=(r-l+1);
st[ind].mid=(r-l+1);
st[ind].laz=0;
st[ind].len=(r-l+1);
if(l==r)
return;
int mid = (l+r)/2;
build(l,mid,ind*2+1);
build(mid+1,r,ind*2+2);
}
node unite(node a, node b){
if(a.val<b.val){
a.len+=b.len;
a.suf=0;
return a;
}
else if(b.val<a.val){
b.len+=a.len;
b.pref=0;
return b;
}
else{
node ans;
ans.laz=0;
ans.len=a.len+b.len;
ans.pref=a.pref+(a.pref==a.len ? b.pref : 0);
ans.suf=b.suf+(b.suf==b.len ? a.suf : 0);
ans.mid=max({a.mid,b.mid,a.suf+b.pref});
ans.val=a.val;
return ans;
}
}
segTree2(int n){
int x = ceil(log2(n));
x++;
st=new node[(1<<x)];
build(0,n-1,0);
}
void push(int ind, int l, int r) {
if(st[ind].laz){
st[ind].val+=st[ind].laz;
if(l<r){
st[ind*2+1].laz+=st[ind].laz;
st[ind*2+2].laz+=st[ind].laz;
}
st[ind].laz=0;
}
}
void update(int l, int r, int s, int e, int ind, int val){
push(ind,l,r);
if(e<l||s>r){
return;
}
if(s<=l&&r<=e){
st[ind].laz=val;
push(ind,l,r);
return;
}
int mid = (l+r)/2;
update(l,mid,s,e,ind*2+1,val);
update(mid+1,r,s,e,ind*2+2,val);
st[ind]=unite(st[ind*2+1],st[ind*2+2]);
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int m,n;
cin >> m >> n;
int b;
cin >> b;
int p;
cin >> p;
array<int,4> evs[p<<1];
for(int i = 0;i<p;i++){
int x1,y1,x2,y2,c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
x1--;x2--;
y1--;y2--;
evs[i]={x1,y1,y2,c};
evs[i+p]={x2+1,y1,y2,-c};
}
segTree st(n);
int lo = 0;
int hi = min(m,n);
while(lo<hi){
int mid = (lo+hi+1)>>1;
if(fin(mid,m,n,evs,p,st)<=b){
lo=mid;
}
else{
hi=mid-1;
}
}
cout << lo;
return 0;
/*
//b is 0 use optimized
vector<array<int,3>>events[m+1];
for(int i = 0;i<2*p;i++){
if(evs[i][3]<0){
evs[i][0]--;
}
events[evs[i][0]].push_back({evs[i][1],evs[i][2],evs[i][3]});
}
segTree2 st(n);
int ans = 0;
int l = 0;
for(int i = 0;i<=m;i++){
for(array<int,3>e:events[i]){
if(e[2]>0){
st.update(0,n-1,e[0],e[1],0,e[2]);
}
}
int b = (i-l+1);
int h = st.st[0].val==0 ? st.st[0].mid : 0;
ans=max(ans,min(b,h));
while(h<b){
for(array<int,3>e:events[l]){
if(e[2]<0){
st.update(0,n-1,e[0],e[1],0,e[2]);
}
}
l++;
b = (i-l+1);
h = st.st[0].val==0 ? st.st[0].mid : 0;
ans=max(ans,min(b,h));
}
}
cout << ans;
return 0;
*/
}
