#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 3005;
int pre_sum[MAX_N][MAX_N];
int a[MAX_N][MAX_N];
// int Sum(int x1, int y1, int x2, int y2) {
// return pre_sum[x2][y2] - pre_sum[x1 - 1][y2] - pre_sum[x2][y1 - 1] + pre_sum[x1 - 1][y1 - 1];
// }
int r, c, h, w, median;
int Ok(int x) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
pre_sum[i][j + 1] = pre_sum[i][j] + (a[i][j] > x);
// pre_sum[i + 1][j + 1] = (a[i][j] > x) + pre_sum[i][j + 1] + pre_sum[i + 1][j] - pre_sum[i][j];
}
}
vi vals(c - w + 1);
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) vals[0] += a[i][j] > x;
}
for (int i = 0; i < h; i++) {
for (int j = 1; j <= c - w; j++) {
vals[j] += (a[i][j + w - 1] > x) - (a[i][j - 1] > x);
}
}
for (int j = 1; j <= c - w; j++) {
vals[j] += vals[j - 1];
}
if (*min_element(all(vals)) <= median) return true;
for (int i = 1; i <= r - h; i++) {
for (int j = 0; j <= c - w; j++) {
vals[j] += pre_sum[i + h - 1][j + w] - pre_sum[i + h - 1][j];
vals[j] -= pre_sum[i - 1][j + w] - pre_sum[i - 1][j];
}
if (*min_element(all(vals)) <= median) return true;
}
return false;
// for (int i = 1; i <= r - h + 1; i++) {
// for (int j = 1; j <= c - w + 1; j++) {
// // int x = Sum(i, j, i + h - 1, j + w - 1);
// if (x <= median) {
// return true;
// }
// }
// }
// return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
r = R, c = C, h = H, w = W;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) a[i][j] = Q[i][j];
}
median = h * w / 2;
int begin = 1, end = r * c, mid;
while (begin < end) {
mid = (begin + end) >> 1;
if (Ok(mid)) end = mid;
else begin = mid + 1;
}
return end;
}
