#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include "quality.h"
using namespace std;
typedef long long ll;
vector<bool> a;
void build(ll l, ll r, ll id, vector<ll>& st){
if(l==r){
if(a[l]){st[id] = 1;}
else{st[id] = 0;}
return;
}
ll m = (l+r)/2;
build(l, m, 2*id, st);
build(m+1, r, 2*id+1, st);
st[id] = st[2*id] + st[2*id+1];
}
void update(ll l, ll r, ll id, ll pos, vector<ll>& st){
if(l==r){st[id] = 1 - st[id]; return;}
ll m = (l+r)/2;
if(pos<=m){update(l, m, 2*id, pos, st);}
else{update(m+1, r, 2*id+1, pos, st);}
st[id] = st[2*id] + st[2*id+1];
}
ll query(ll l, ll r, ll id, ll c, vector<ll>& st){
if(l==r){return l;}
ll m = (l+r)/2;
if(c > st[2*id]){return query(m+1, r, 2*id+1, c - st[2*id], st);}
else{return query(l, m, 2*id, c, st);}
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
ll ans = -1;
a.clear();
a.resize(R*C, false);
vector<ll> st1(4*R*C + 5);
for(ll i=0;i<H;i++){
for(ll j=0;j<W;j++){
a[R*C - Q[i][j]] = true;
}
}
build(0, R*C-1, 1, st1);
for(ll i=H;i<R;i++){
ans = max(ans, query(0, R*C - 1, 1, (H*W+1)/2, st1));
vector<ll> st2 = st1;
for(ll j=W;j<C;j++){
for(ll k=i-H;k<i;k++){
update(0, R*C-1, 1, R*C - Q[k][j-W], st2);
update(0, R*C-1, 1, R*C - Q[k][j], st2);
}
ans = max(ans, query(0, R*C - 1, 1, (H*W+1)/2, st2));
}
for(ll j=0;j<W;j++){
update(0, R*C-1, 1, R*C - Q[i-H][j], st1);
update(0, R*C-1, 1, R*C - Q[i][j], st1);
}
}
return R*C - ans;
}
