#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
namespace sub12 {
const int maxN = 1e6 + 20;
int tree[maxN << 2];
int lazy[maxN << 2];
int Lx[maxN];
int Ly[maxN];
int Rx[maxN];
int Ry[maxN];
int cost[maxN];
vector<int> queries[maxN];
int N, M, B, K;
void reset(int id, int lt, int rt) {
tree[id] = 0;
lazy[id] = 0;
if (lt == rt) {
return;
}
int mt = (lt + rt) >> 1;
reset(id << 1, lt, mt);
reset(id << 1 | 1, mt + 1, rt);
}
void update(int id, int lt, int rt, int ql, int qr, int add) {
if (lt == ql && rt == qr) {
tree[id] += add;
lazy[id] += add;
return;
}
tree[id << 1] += lazy[id];
lazy[id << 1] += lazy[id];
tree[id << 1 | 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
lazy[id] = 0;
int mt = (lt + rt) >> 1;
if (qr <= mt) {
update(id << 1, lt, mt, ql, qr, add);
}
else if (ql >= mt + 1) {
update(id << 1 | 1, mt + 1, rt, ql, qr, add);
}
else {
update(id << 1, lt, mt, ql, mt, add);
update(id << 1 | 1, mt + 1, rt, mt + 1, qr, add);
}
tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
}
bool check(int sz) {
int n = N - sz + 1;
int m = M - sz + 1;
for (int i = 1; i <= n; i++) {
queries[i].clear();
}
for (int i = 1; i <= K; i++) {
int lx = max(1, Lx[i] - sz + 1);
int rx = min(n, Rx[i]);
int ly = max(1, Ly[i] - sz + 1);
int ry = min(m, Ry[i]);
if (lx <= rx && ly <= ry) {
queries[lx].push_back(i);
if (rx < n) {
queries[rx + 1].push_back(-i);
}
}
}
reset(1, 1, m);
for (int i = 1; i <= n; i++) {
for (auto id: queries[i]) {
if (id > 0) {
int lt = max(1, Ly[id] - sz + 1);
int rt = min(m, Ry[id]);
update(1, 1, m, lt, rt, cost[id]);
}
else {
int lt = max(1, Ly[-id] - sz + 1);
int rt = min(m, Ry[-id]);
update(1, 1, m, lt, rt, -cost[-id]);
}
}
if (tree[1] <= B) {
return true;
}
}
return false;
}
void solve() {
for (int i = 1; i <= K; i++) {
cin >> Lx[i] >> Ly[i] >> Rx[i] >> Ry[i] >> cost[i];
}
int res = 0;
int lt = 1;
int rt = min(N, M);
while (lt <= rt) {
int mt = (lt + rt) >> 1;
if (check(mt)) {
res = mt;
lt = mt + 1;
}
else {
rt = mt - 1;
}
}
cout << res;
}
}
void just_do_it() {
int N, M, B, K;
cin >> N >> M >> B >> K;
if (B > 0 || K <= 1000) {
sub12::N = N;
sub12::M = M;
sub12::B = B;
sub12::K = K;
sub12::solve();
}
}
