#include <iostream>
#include "quality.h"
using namespace std;
int n, m, high, wide;
int const NMAX = 3000;
int mat[1 + NMAX][1 + NMAX];
int presum[1 + NMAX][1 + NMAX];
void buildPresum(int lim) {
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
presum[i][j] = presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1];
if(lim < mat[i][j]) {
presum[i][j]++;
}
}
}
}
bool isGood() {
for(int i = high;i <= n;i++) {
for(int j = wide;j <= m;j++) {
int sum = presum[i][j] - presum[i-high][j] - presum[i][j-wide] + presum[i-high][j-wide];
if(sum + sum < high * wide) {
return true;
}
}
}
return false;
}
int cautbin(int from, int to) {
if(from >= to) {
return from;
} else {
int mid = (from + to) / 2;
buildPresum(mid);
if(isGood()) {
return cautbin(from, mid);
}else {
return cautbin(mid+1, to);
}
}
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
n = R;
m = C;
high = H;
wide = W;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
mat[i][j] = Q[i-1][j-1];
}
}
return cautbin(1, R * C);
}
