#include <bits/stdc++.h>
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
using namespace std;
typedef unsigned ll;
int base = 1;
ll inf = 4e09;
struct event{
int y1, y2; ll c;
event(){}
event(int y1, int y2, ll c) : y1(y1), y2(y2), c(c){}
};
struct seg{
vector<ll> t, p;
void init(int n){
while(base < n) base<<=1;
t.resize(base<<1|1);
p.resize(base<<1|1);
} void purge(){for(int i = 1; i <= base<<1; ++i) t[i] = p[i] = 0;};
void add(int i, ll ile){t[i] += ile, p[i] += ile;}
void push(int i){
add(i<<1, p[i]);
add(i<<1|1, p[i]);
p[i] = 0;
} void update(int i, int pocz, int kon, int x, int y, ll w){
if(x <= pocz && kon <= y) return void(add(i, w));
push(i);
int sr = (pocz+kon) >> 1;
if(x <= sr) update(i<<1, pocz, sr, x, y, w);
if(sr < y) update(i<<1|1, sr+1, kon, x, y, w);
t[i] = MIN(t[i<<1], t[i<<1|1]);
}
} seg;
bool zamiatanie(int n, int m, int y, ll w, vector<vector<event>>& p, vector<vector<event>>& k){
seg.purge();
if(1 < y) seg.update(1, 1, base, 1, y-1, inf);
if(m < base) seg.update(1, 1, base, m+1, base, inf);
int pc, kn;
for(int i = 1; i <= y; ++i)
for(event u : p[i]){
pc = MAX(y, u.y1), kn = MIN(m, u.y2+y-1);
//if(pc <= kn)
seg.update(1, 1, base, pc, kn, u.c);
}
ll wynik = seg.t[1];
for(int i = y+1; i <= n; ++i){
for(event u : p[i]){
pc = MAX(y, u.y1), kn = MIN(m, u.y2+y-1);
//if(pc <= kn)
seg.update(1, 1, base, pc, kn, u.c);
}
for(event u : k[i-y]){
pc = MAX(y, u.y1), kn = MIN(m, u.y2+y-1);
//if(pc <= kn)
seg.update(1, 1, base, pc, kn, -u.c);
}
wynik = MIN(wynik, seg.t[1]);
}
if(w < wynik) return 0;
else return 1;
}
int main(){
int n, m, w, q, x1, y1, x2, y2, c;
scanf("%d%d%d%d", &n, &m, &w, &q);
vector<vector<event>> p(n+1), k(n+1);
seg.init(m);
for(int i = q+1; --i; ){
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
p[x1].emplace_back(y1, y2, c);
k[x2].emplace_back(y1, y2, c);
} int pocz = 1, kon = MIN(n, m), y;
bool b = zamiatanie(n, m, 1, w, p, k);
if(!b){printf("0\n"); return 0;}
while(pocz != kon){
y = ((pocz + kon) >> 1) + 1; // y to nasz sr w binserczu
b = zamiatanie(n, m, y, w, p, k);
if(!b) kon = y - 1;
else pocz = y;
}
printf("%d\n", pocz);
return 0;
}
