#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep2(i, m ,n) for (int i = (m); i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i < (long long)(n); i++)
typedef long long ll;
#define l(n) n.begin(),n.end()
#define YesNo(Q) Q==1?cout<<"Yes":cout<<"No"
struct S {
int sum;
int pre_min;
};
S e() {
return {0, (int)(2e9)+2};
}
S op(S a, S b) {
return {a.sum + b.sum, min(a.pre_min, a.sum + b.pre_min)};
}
template<class S, S(*e)(), S(*op)(S,S)>
struct segtree {
int n;
vector<S> node;
segtree(vector<S> v) {
n = 1;
while (n < (int)v.size()) n *= 2;
node.assign(2 * n, e());
rep(i, (int)v.size()) node[n - 1 + i] = v[i];
for (int i = n - 2; i >= 0; i--) {
node[i] = op(node[2 * i + 1], node[2 * i + 2]);
}
}
void set(int p, S x) {
p += n - 1;
node[p] = x;
while (p > 0) {
p = (p - 1) / 2;
node[p] = op(node[2 * p + 1], node[2 * p + 2]);
}
}
S get(int p) {
return node[p + n - 1];
}
S sum(int a, int b, int k = 0, int l = 0, int r = -1) {
if (r == -1) r = n;
if (b <= l || r <= a) return e();
if (a <= l && r <= b) return node[k];
return op(sum(a, b, 2 * k + 1, l, (l + r) / 2),
sum(a, b, 2 * k + 2, (l + r) / 2, r));
}
};
struct obb{
int x1, y1, x2, y2;
ll cost;
};
struct Event {
int x;
int y1, y2;
ll cost;
bool operator<(const Event& o) const {
return x < o.x;
}
};
bool check(int K, int M, int N, ll B, const vector<obb>& obs) {
int max_x = M - K + 1;
int max_y = N - K + 1;
if (max_x < 1 || max_y < 1) return false;
vector<Event> events;
events.reserve(obs.size() * 2);
for (const auto& ob : obs) {
int lx = max(1, ob.x1 - K + 1);
int rx = min(max_x, ob.x2);
int ly = max(1, ob.y1 - K + 1);
int ry = min(max_y, ob.y2);
if (lx <= rx && ly <= ry) {
events.push_back({lx, ly, ry, ob.cost});
events.push_back({rx + 1, ly, ry, -ob.cost});
}
}
sort(l(events));
if (events.empty() || events[0].x > 1) return true;
vector<S> init_v(max_y + 2, {0, 0});
segtree<S, e, op> seg(init_v);
vector<ll> D(max_y + 2, 0);
int ev_idx = 0;
int num_events = events.size();
while (ev_idx < num_events) {
int cur_x = events[ev_idx].x;
if (cur_x > max_x) break;
while (ev_idx < num_events && events[ev_idx].x == cur_x) {
const auto& ev = events[ev_idx];
D[ev.y1] += ev.cost;
seg.set(ev.y1, {D[ev.y1], D[ev.y1]});
D[ev.y2 + 1] -= ev.cost;
seg.set(ev.y2 + 1, {D[ev.y2 + 1], D[ev.y2 + 1]});
ev_idx++;
}
ll min_cost = seg.sum(1, max_y + 1).pre_min;
if (min_cost <= B) return true;
}
return false;
}
int main(){
int n,m,b,p;cin>>m>>n>>b>>p;
vector<obb> obs(p);
rep(i, p) {
cin >> obs[i].x1 >> obs[i].y1 >> obs[i].x2 >> obs[i].y2 >> obs[i].cost;
}
int ok = 0;
int ng = min(n, m) + 1;
while (ng - ok > 1) {
int mid = ok + (ng - ok) / 2;
if (check(mid, m, n, b, obs)) {
ok = mid;
} else {
ng = mid;
}
}
cout << ok << endl;
return 0;
}
