#include <iostream>
#include <cmath>
using namespace std;
const int NMAX = 3000;
int maxx, ans, mid, LOG;
int aib[NMAX * NMAX + 2];
void update(int pos, int val) {
while(pos <= maxx) {
aib[pos] += val;
pos += pos & (-pos);
}
}
int check() { ///de gasit mediana
int pos = 0;
int cnt = 0; ///suma curenta
for(int bit = LOG; bit >= 0; bit--) {
if(pos + (1 << bit) <= maxx && cnt + aib[pos + (1 << bit)] < mid) {
pos += (1 << bit);
cnt += aib[pos];
}
}
return pos + 1;
}
int v[NMAX + 1][NMAX + 1];
int rectangle(int n, int m, int r, int c, int q[NMAX + 1][NMAX + 1]) {
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
v[i][j] = q[i][j];
maxx = n * m;
ans = n * m + 1;
mid = (r * c + 1) / 2;
LOG = log2(n * m);
///INIT PT AIB
for(int i = 1; i <= r; i++) {
for(int j = 1; j <= c; j++) {
update(v[i][j], 1);
}
}
int ultlin = n - r + 1, ultcol;
bool sens = 0; ///0 --> dr, 1 --> st
if(ultlin % 2 == 0)
ultcol = 1;
else
ultcol = m - c + 1;
int i = 1, j = 1; ///coltul din st sus
while(1) {
//cout << i << " " << j << " " << check() << '\n';
ans = min(ans, check()); ///ver unde am ajuns
if(i == ultlin && j == ultcol) ///am term, done
break;
if(!sens) { ///o luam in dr
if(j + c - 1 == m) { ///am ajuns la fin
for(int col = j; col <= m; col++) {
update(v[i][col], -1); ///scoatem vechi
update(v[i + r][col], 1); ///luam nou
}
i++;
sens = 1;
}
else { ///scoatem col veche
for(int lin = i; lin <= i + r - 1; lin++) {
update(v[lin][j], -1);
update(v[lin][j + c], 1);
}
j++;
}
}
else { ///o luam in st
if(j == 1) { ///fin
for(int col = 1; col <= c; col++) {
update(v[i][col], -1);
update(v[i + r][col], 1);
}
i++;
sens = 0;
}
else { ///ne shiftam la dr
for(int lin = i; lin <= i + r - 1; lin++) {
update(v[lin][j + c - 1], -1);
update(v[lin][j - 1], 1);
}
j--;
}
}
}
return ans;
}
