#include<bits/stdc++.h>
#define endl '\n'
#define ull unsigned long long int
// vnimavai za otricatelni
using namespace std;
const int maxn = 3003;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int pref[maxn][maxn], n, m, h, w, q[maxn][maxn], cur, e[3001][3001];
bool check(int x)
{
memset(pref, 0, sizeof(pref));
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
pref[i][j] = (pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]);
if(q[i][j] <= x)
pref[i][j]++;
}
}
for(int i = h; i <= n; i++)
{
for(int j = w; j <= m; j++)
{
int curr = pref[i][j] - pref[i - h][j] - pref[i][j - w] + pref[i - h][j - w];
if(curr > h * w / 2)
return 1;
}
}
return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
n = R;
m = C;
h = H;
w = w;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
q[i][j] = Q[i-1][j-1];
}
}
int l = 0, r = n * m, ans = 0;
while (r - l >= 0)
{
int mid = l + (r - l) / 2;
if (check(mid))
{
r = mid - 1;
ans = mid;
}
else
l = mid + 1;
}
return ans;
}
/*int main()
{
speed();
cin >> n >> m >> h >> w;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
cin >> e[i][j];
}
}
cout << rectangle(n, m, h, w, e) << endl;
return 0;
}*/
