#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; } }