#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, h, w;
int (*a)[3001];
int pref[3020][3020];
int get(int lx, int ly, int rx, int ry) {
return pref[rx][ry] - pref[rx][ly - 1] - pref[lx - 1][ry] + pref[lx - 1][ly - 1];
}
bool check(int x) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
pref[i + 1][j + 1] = (a[i][j] <= x ? 1 : -1);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
pref[i][j] += pref[i][j - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
pref[i][j] += pref[i - 1][j];
}
}
for (int i = h; i <= n; i++) {
for (int j = w; j <= m; j++) {
if (get(i - h + 1, j - w + 1, i, j) > 0) {
return true;
}
}
}
return false;
}
int rectangle(int _n, int _m, int _h, int _w, int _a[3001][3001]) {
n = _n;
m = _m;
h = _h;
w = _w;
a = _a;
int res = -1;
int lt = 1;
int rt = n * m;
while (lt <= rt) {
int mt = (lt + rt) / 2;
if (check(mt)) {
res = mt;
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
return res;
}
