#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define int long long
using namespace std;
const int N=1e6+5,K=1<<21,INF=1e18;
int m,n,p,b;
vector<tuple<int,int,int>> add[N],del[N];
struct blk{
int val,sz;
bool operator<(const blk &o)const{return val<o.val||(val==o.val&&sz>o.sz);}
};
struct node{
int sz;
blk mn,pre,suf;
node():sz(0),mn({INF,0}),pre({INF,0}),suf({INF,0}){}
static node single(){node res;res.sz=1;res.mn=res.pre=res.suf={0,1};return res;}
void apply(int v){mn.val+=v,pre.val+=v,suf.val+=v;}
friend node operator+(const node &a,const node &b){
node res;
res.mn=min(a.mn,b.mn);
if(a.suf.val==b.pre.val)res.mn=min(res.mn,{a.suf.val,a.suf.sz+b.pre.sz});
res.pre=a.pre;
if(a.pre.val==b.pre.val&&a.pre.sz==a.sz)res.pre.sz+=b.pre.sz;
res.suf=b.suf;
if(a.suf.val==b.suf.val&&b.suf.sz==b.sz)res.suf.sz+=a.suf.sz;
res.sz=a.sz+b.sz;
return res;
}
};
struct seg1{
int t[K],lz[K];
void apply(int i,int v){t[i]+=v,lz[i]+=v;}
void push(int i){apply(i*2,lz[i]),apply(i*2+1,lz[i]),lz[i]=0;}
void build(int l,int r,int i){
t[i]=0,lz[i]=0;
if(l==r)return;
int mid=(l+r)/2;
build(l,mid,i*2),build(mid+1,r,i*2+1);
}
void build(){build(1,n,1);}
void update(int l,int r,int i,int x,int y,int v){
if(y<l||r<x)return;
if(x<=l&&r<=y)return apply(i,v);
int mid=(l+r)/2;
push(i),update(l,mid,i*2,x,y,v),update(mid+1,r,i*2+1,x,y,v),t[i]=min(t[i*2],t[i*2+1]);
}
void update(int x,int y,int v){update(1,n,1,x,y,v);}
}sg1;
bool chk(int k){
sg1.build(),sg1.update(1,k-1,INF);
for(int i=1;i<k;i++)for(auto [l,r,v]:add[i])sg1.update(l,r+k-1,v);
for(int i=k;i<=m;i++){
for(auto [l,r,v]:add[i])sg1.update(l,r+k-1,v);
for(auto [l,r,v]:del[i-k])sg1.update(l,r+k-1,-v);
if(sg1.t[1]<=b)return 1;
}
return 0;
}
struct seg2{
node t[K];
int lz[K];
void apply(int i,int v){t[i].apply(v),lz[i]+=v;}
void push(int i){apply(i*2,lz[i]),apply(i*2+1,lz[i]),lz[i]=0;}
void pull(int i){t[i]=t[i*2]+t[i*2+1];}
void build(int l,int r,int i){
lz[i]=0;
if(l==r)return t[i]=node::single(),void();
int mid=(l+r)/2;
build(l,mid,i*2),build(mid+1,r,i*2+1),pull(i);
}
void build(){build(1,n,1);}
void update(int l,int r,int i,int x,int y,int v){
if(y<l||r<x)return;
if(x<=l&&r<=y)return apply(i,v);
int mid=(l+r)/2;
push(i),update(l,mid,i*2,x,y,v),update(mid+1,r,i*2+1,x,y,v),pull(i);
}
void update(int x,int y,int v){update(1,n,1,x,y,v);}
}sg2;
signed main(void){
exoworldgd;
cin>>m>>n>>b>>p;
for(int i=0,x1,y1,x2,y2,c;i<p;i++) cin>>x1>>y1>>x2>>y2>>c, add[x1].emplace_back(y1,y2,c), del[x2].emplace_back(y1,y2,c);
if(b>0){
int l=0,r=min(n,m);
while(l<r){
int mid=(l+r+1)/2;
if(chk(mid))l=mid;
else r=mid-1;
}
cout<<l;
}else{
sg2.build();
int top=0,bot=0,ans=0;
while(bot<=m){
auto x=sg2.t[1].mn;
int h=bot-top,w=x.val==0?x.sz:0;
ans=max(ans,min(h,w));
if(h<=w){
bot++;
for(auto [l,r,v]:add[bot])sg2.update(l,r,v);
}else{
top++;
for(auto [l,r,v]:del[top])sg2.update(l,r,-v);
}
}
cout<<ans;
}
}
