#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define fi first
#define se second
#define pii pair<int, int>
#define sz(x) (int)(x).size()
const int M = 1e6 + 5;
struct Node{
int val, len, suff, pref, ans, lazy;
Node(int v, int l, int s, int p, int a, int lz) : val(v), len(l), suff(s), pref(p), ans(a), lazy(lz) {}
Node(int l) : Node(0, l, l, l, l, 0) {}
Node() : Node(0, 0, 0, 0, 0, 0) {}
};
struct SegTree{
int n;
vector<Node> st;
SegTree(int n) : n(n), st(4 * n) {}
inline Node combine(const Node &a, const Node &b){
Node c;
c.len = a.len + b.len;
if(a.val > b.val){
c.val = b.val;
c.ans = b.ans;
c.pref = 0;
c.suff = b.suff;
}
else if(a.val < b.val){
c.val = a.val;
c.ans = a.ans;
c.pref = a.pref;
c.suff = 0;
}
else{
c.val = a.val;
c.suff = b.suff;
if(b.ans == b.len){
c.suff = b.ans + a.suff;
}
c.pref = a.pref;
if(a.ans == a.len){
c.pref = a.ans + b.pref;
}
c.ans = max({a.ans, b.ans, a.suff + b.pref});
}
return c;
}
inline void build(int v, int tl, int tr){ // wtf???????
if(tl == tr){
st[v] = Node(1);
return;
}
int mid = (tl + tr) / 2;
build(2 * v, tl, mid);
build(2 * v + 1, mid + 1, tr);
st[v] = combine(st[2 * v], st[2 * v + 1]);
return;
}
inline void build(){
build(1, 1, n);
return;
}
inline void apply(int v, int val){
st[v].val += val;
st[v].lazy += val;
return;
}
inline void propagate(int v){
apply(2 * v, st[v].lazy);
apply(2 * v + 1, st[v].lazy);
st[v].lazy = 0;
return;
}
inline void update(int ul, int ur, int val, int v, int tl, int tr){
if(ul > tr || tl > ur) return;
if(ul <= tl && tr <= ur){
apply(v, val);
return;
}
int mid = (tl + tr) / 2;
propagate(v);
update(ul, ur, val, 2 * v, tl, mid);
update(ul, ur, val, 2 * v + 1, mid + 1, tr);
st[v] = combine(st[2 * v], st[2 * v + 1]);
return;
}
inline void update(int ul, int ur, int val){
if(ul > ur) return;
update(max(ul + 1, 1ll), min(ur + 1, n), val, 1, 1, n);
return;
}
};
inline void solve(){
int m, n, budget, p;
cin >> n >> m >> budget >> p;
vector<array<int, 5>> ob(p);
for(int i = 0; i < p; i++){ // {x1, y1, x2, y2, c}
cin >> ob[i][0] >> ob[i][1] >> ob[i][2] >> ob[i][3] >> ob[i][4];
ob[i][0]--, ob[i][1]--, ob[i][2]--, ob[i][3]--;
}
auto solve0 = [&]() -> int {
vvi add(n), er(n);
for(int i = 0; i < p; i++){
add[ob[i][0]].emplace_back(i);
er[ob[i][2]].emplace_back(i);
}
int ans = 0;
SegTree st(m);
st.build();
for(int le = 0, ri = -1; le < n; le++){
while(ri < n){
if(st.st[1].val || st.st[1].ans < ri - le + 1) break;
ri++;
for(int &idx : add[ri]){
array<int, 5> r = ob[idx];
st.update(r[1], r[3], 1);
}
}
ans = max(ans, (ri - 1) - le + 1); // just before the last addition on ri
for(int &idx : er[le]){
array<int, 5> r = ob[idx];
st.update(r[1], r[3], -1);
}
}
return ans;
};
auto solve1 = [&]() -> int {
auto check = [&](int len) -> bool {
//cout << "len: " << len << "\n";
vvi pos(n + 1);
SegTree st(m - len + 1);
for(int i = 0; i < p; i++){
int lx = max(ob[i][0] - len + 1, 0ll), rx = ob[i][2];
pos[lx].emplace_back(i), pos[rx + 1].emplace_back(i);
}
for(int i = 0; i < n - len + 1; i++){
for(int &idx : pos[i]){
int dy = max(ob[idx][1] - len + 1, 0ll), uy = ob[idx][3], c = (i == ob[idx][2] + 1 ? -ob[idx][4] : ob[idx][4]);
//cout << "idx: " << idx << " dy: " << dy << " uy: " << uy << " c: " << c << "\n";
st.update(dy, uy, c);
}
if(st.st[1].val <= budget) return true;
}
return false;
};
auto bs = [&]() -> int {
int lo = 1, hi = min(n, m), ret = 0, mid;
while(hi >= lo){
mid = lo + (hi - lo) / 2;
if(check(mid)){
lo = mid + 1;
ret = mid;
}
else{
hi = mid - 1;
}
}
return ret;
};
return bs();
};
cout << (budget ? solve1() : solve0()) << "\n";
return;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
