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