#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int RR = 3100;
const int CC = 3100;
ll prefixMat[RR][CC];
ll prefixRows[RR][CC];
ll prefixCols[CC][RR];
bool cando(int k, int R, int C, int H, int W, int Q[3001][3001]) {
// make prefix Rows
// 0 of Q is 1 of prefixRows
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
int I = i + 1;
int J = j + 1;
prefixRows[I][J] = prefixRows[I][J - 1];
if (Q[i][j] < k) {
prefixRows[I][J] -= 1;
} else if (Q[i][j] > k) {
prefixRows[I][J] += 1;
}
}
}
for (int j = 0; j < C; j++) {
for (int i = 0; i < R; i++) {
int I = i + 1;
int J = j + 1;
prefixCols[J][I] = prefixCols[J][I - 1];
if (Q[i][j] < k) {
prefixCols[J][I] -= 1;
} else if (Q[i][j] > k) {
prefixCols[J][I] += 1;
}
}
}
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
prefixMat[i][j] = prefixMat[i][j-1] + prefixCols[j][i];
}
}
for (int i = 1; i + H - 1 <= R; i++) {
for (int j = 1; j + W - 1 <= C; j++) {
if (prefixMat[i + H - 1][j + W - 1] - prefixMat[i + H - 1][j - 1] - prefixMat[i - 1][j + W - 1] + prefixMat[i-1][j-1] >= 0) {
return true;
}
}
}
return false;
}
int rectangle(int R,int C,int H,int W,int Q[3001][3001]) {
int lo = 1;
int hi = R * C;
int best = 1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (cando(mid, R, C, H, W, Q)) {
best = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return best;
}
