#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define each(i,x) for(auto i:x)
#define all(x) x.begin(),x.end()
using ll=long long;
#define fi first
#define se second
struct SegTree{
using T=pair<int,int>;
static T op(T x,T y){
return {x.fi+y.fi,min(x.se,x.fi+y.se)};
}
static inline T e={0,0};
vector<T> val;
int n;
SegTree(int sz){
n=sz;
while(n!=(n&(-n)))n++;
val.resize(n*2,e);
}
void static_set(int p,T v){
p+=n;
val[p]=v;
}
void all_affect(){
for(int p=n-1; p>=1; p--){
val[p]=op(val[p*2],val[p*2+1]);
}
}
void set(int p,T v){
p+=n;
val[p]=v;
p/=2;
while(p>=1){
val[p]=op(val[p*2],val[p*2+1]);p/=2;
}
}
inline T get(int p){
return val[p+n];
}
T all_prod(){
return val[1];
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,M;cin>>N>>M;
ll b;cin>>b;int B=min(b,300000000LL);
int P;cin>>P;
vector<array<int,5>> rect(P);
rep(i,P){
rep(j,5){
cin>>rect[i][j];
if(j<=1)rect[i][j]--;
}
rect[i][4]=min(rect[i][4],B+1);
}
vector<pair<int,int>> s1(P),s2(P);
rep(i,P){
s1[i]={rect[i][1],i};
s2[i]={rect[i][3],i};
}
sort(all(s1));sort(all(s2));
int ok=0,ng=min(N,M)+1;
while(ng-ok>1){
int mid=(ok+ng)/2;
vector<array<int,4>> seg(P*2);
rep(i,P){
int a=rect[i][0],b=rect[i][1],c=rect[i][2],d=rect[i][3];
a-=mid-1;b-=mid-1;
a=max(0,a);b=max(0,b);c=min(c,N-mid+1);d=min(d,M-mid+1);
seg[i]={b,a,c,rect[i][4]};
seg[i+P]={d,a,c,-rect[i][4]};
}
sort(all(seg));
SegTree segt(N-mid+1);
rng(i,1,N-mid+1){
segt.static_set(i,{0,0});
}
bool flg=false;
segt.all_affect();
int f=0;
int pp=0,ppp=0;
rep(i,M-mid+1){
while(pp<P&&max(0,s1[pp].fi-mid+1)==i){
int id=s1[pp].se;
array<int,3> j={max(0,rect[id][0]-mid+1),min(rect[id][2],N-mid+1),rect[id][4]};
pp++;
auto p=segt.get(j[0]);
if(j[0]!=0){
p.fi+=j[2];p.se=min(0,p.fi);
segt.set(j[0],p);
}
else{
f+=j[2];
}
if(j[1]!=N-mid+1){
p=segt.get(j[1]);
p.fi-=j[2];p.se=min(0,p.fi);
segt.set(j[1],p);
}
}
while(ppp<P&&min(M-mid+1,s2[ppp].fi)==i){
int id=s2[ppp].se;
array<int,3> j={max(0,rect[id][0]-mid+1),min(rect[id][2],N-mid+1),-rect[id][4]};
ppp++;
auto p=segt.get(j[0]);
if(j[0]!=0){
p.fi+=j[2];p.se=min(0,p.fi);
segt.set(j[0],p);
}
else{
f+=j[2];
}
if(j[1]!=N-mid+1){
p=segt.get(j[1]);
p.fi-=j[2];p.se=min(0,p.fi);
segt.set(j[1],p);
}
}
auto pr=segt.all_prod();
if(f+pr.se<=B){
flg=true;break;
}
}
if(flg)ok=mid;
else ng=mid;
}
cout<<ok<<"\n";
}
