#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = (3e3) + 5;
int a[MAX][MAX], n, m, h, w;
int pre[MAX][MAX];
bool Checker(int k)
{
int op;
for (int i = 1; i <= n; i++)
{
op = 0;
for (int j = 1; j <= m; j++)
{
op += (bool)(a[i][j] <= k);
pre[i][j] = pre[i - 1][j] + op;
}
}
int cnt;
for (int i = h; i <= n; i++)
{
for (int j = w; j <= m; j++)
{
cnt = pre[i][j] - pre[i - h][j] - pre[i][j - w] + pre[i - h][j - w];
if (cnt > h * w / 2)
return 1;
}
}
return 0;
}
int Binary()
{
int l = 0, r = n * m, mid;
while (r - l > 1)
{
mid = l + (r - l) / 2;
if (Checker(mid))
r = mid;
else
l = mid;
}
return r;
}
int rectangle(int N, int M, int H, int W, int A[3001][3001])
{
n = N;
m = M;
h = H;
w = W;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
a[i][j] = A[i - 1][j - 1];
}
return Binary();
}
