#include <cstdio>
#include <algorithm>
using namespace std;
int r, c, h, w, prefix[3001][3001];
void update(int i, int j, int delta) {
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + delta;
}
int query(int x1, int y1, int x2, int y2) {
return prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1];
}
bool work(int x, int grid[3001][3001], int r, int c, int h, int w) {
for (int i=0; i<=r; i++) {
prefix[i][0] = 0;
}
for (int j=0; j<=c; j++) {
prefix[0][j] = 0;
}
for (int i=1; i<=r; i++) {
for (int j=1; j<=c; j++) {
if (grid[i-1][j-1]>x) {
update(i, j, -1);
} else if (grid[i-1][j-1]==x) {
update(i, j, 0);
} else {
update(i, j, 1);
}
}
}
for (int i=1; i<=r-h+1; i++) {
for (int j=1; j<=c-w+1; j++) {
if (query(i, j, i+h-1, j+w-1) >= 0) return true;
}
}
return false;
}
int rectangle(int r, int c, int h, int w, int grid[3001][3001]) {
int low=1, high=r*c, mid;
while (low != high) {
mid = (low+high)>>1;
if (!work(mid, grid, r, c, h, w)) {
low = mid+1;
} else {
high = mid;
}
}
return low;
}
