#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e6;
const int MAXP = 4e5;
const ll INF = 1e18;
struct Rect
{
int x1, y1, x2, y2, w;
};
struct Line
{
int x, y1, y2, w;
bool operator < (const Line &p) const { return x<p.x; }
};
int N, M, P;
ll B;
Rect A[MAXP+10];
struct SEG
{
ll tree[MAXN*4+10], lazy[MAXN*4+10];
void init()
{
memset(tree, 0, sizeof(tree));
memset(lazy, 0, sizeof(lazy));
}
void busy(int node, int tl, int tr)
{
tree[node]+=lazy[node];
if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
lazy[node]=0;
}
void update(int node, int tl, int tr, int l, int r, ll v)
{
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
lazy[node]+=v;
busy(node, tl, tr);
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, v);
update(node*2+1, mid+1, tr, l, r, v);
tree[node]=min(tree[node*2], tree[node*2+1]);
}
}seg;
bool solve(int d)
{
int i, j;
vector<Line> V;
ll val=INF;
for(i=1; i<=P; i++)
{
V.push_back({A[i].x1, A[i].y1, A[i].y2+d-1, A[i].w});
V.push_back({A[i].x2+d, A[i].y1, A[i].y2+d-1, -A[i].w});
}
sort(V.begin(), V.end());
seg.init();
for(i=0; i<V.size();)
{
int x=V[i].x;
seg.busy(1, d, N);
if(d<=x-1) val=min(val, seg.tree[1]);
if(x>M) break;
for(; i<V.size() && V[i].x==x; i++)
{
seg.update(1, d, N, V[i].y1, V[i].y2, V[i].w);
}
}
seg.busy(1, d, N);
val=min(val, seg.tree[1]);
if(val<=B) return true;
return false;
}
int main()
{
int i, j;
scanf("%d%d%lld%d", &M, &N, &B, &P);
for(i=1; i<=P; i++) scanf("%d%d%d%d%d", &A[i].x1, &A[i].y1, &A[i].x2, &A[i].y2, &A[i].w);
int lo=0, hi=min(N, M)+1;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(solve(mid)) lo=mid;
else hi=mid;
}
printf("%d\n", lo);
}
