#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000;
struct segment_tree{
int N;
vector<long long> sum, left;
segment_tree(int N2){
N = 1;
while (N < N2){
N *= 2;
}
sum = vector<long long>(N * 2 - 1, INF);
left = vector<long long>(N * 2 - 1, INF);
for (int i = 0; i < N2; i++){
sum[N - 1 + i] = 0;
left[N - 1 + i] = 0;
}
for (int i = N - 2; i >= 0; i--){
sum[i] = sum[i * 2 + 1] + sum[i * 2 + 2];
left[i] = 0;
}
}
void add(int i, long long x){
i += N - 1;
sum[i] += x;
left[i] = sum[i];
while (i > 0){
i = (i - 1) / 2;
sum[i] = sum[i * 2 + 1] + sum[i * 2 + 2];
left[i] = min(left[i * 2 + 1], sum[i * 2 + 1] + min(left[i * 2 + 2], (long long) 0));
}
}
long long get(){
return left[0];
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int M, N;
cin >> M >> N;
int B;
cin >> B;
int P;
cin >> P;
vector<int> X1(P), Y1(P), X2(P), Y2(P), C(P);
for (int i = 0; i < P; i++){
cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i] >> C[i];
X1[i]--;
Y1[i]--;
}
int tv = 0, fv = min(M, N) + 1;
vector<vector<int>> add(N), sub(N);
while (fv - tv > 1){
int mid = (tv + fv) / 2;
for (int i = 0; i < P; i++){
add[max(Y1[i] - mid + 1, 0)].push_back(i);
if (Y2[i] < N - mid + 1){
sub[Y2[i]].push_back(i);
}
}
segment_tree ST(M - mid + 1);
bool ok = false;
for (int i = 0; i < N - mid + 1; i++){
for (int j : add[i]){
ST.add(max(X1[j] - mid + 1, 0), C[j]);
if (X2[j] < M - mid + 1){
ST.add(X2[j], -C[j]);
}
}
add[i].clear();
for (int j : sub[i]){
ST.add(max(X1[j] - mid + 1, 0), -C[j]);
if (X2[j] < M - mid + 1){
ST.add(X2[j], C[j]);
}
}
sub[i].clear();
if (ST.get() <= B){
ok = true;
}
}
if (ok){
tv = mid;
} else {
fv = mid;
}
}
cout << tv << endl;
}
