#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int c[3001][3001], pref[3001][3001];
int r1, c1, h1, w1;
int q[3001][3001];
bool check(int x)
{
int a, b;
for(int i = 1; i <= r1; i++)
{
for(int j = 1; j <= c1; j++)
{
if(q[i][j] <= x)c[i][j] = 0;
else c[i][j] = 1;
if(q[i][j] == x)
{
a = i;
b = j;
}
}
}
for(int i = 1; i <= r1; i++)
{
for(int j = 1; j <= c1; j++)
{
pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + c[i][j];
}
}
for(int i = h1; i <= r1; i++)
{
for(int j = w1; j <= c1; j++)
{
int cnt = pref[i][j] - pref[i-h1][j] - pref[i][j-w1] + pref[i-h1][j-w1];
///cout << x << " " << i << " " << j << " " << cnt << endl;
if(cnt == h1*w1/2 && i-a >= 0 && i-a < h1 && j-b >= 0 && j-b < w1)
return true;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
int l = 1, r = R*C;
r1 = R;
c1 = C;
h1 = H;
w1 = W;
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
q[i+1][j+1] = Q[i][j];
}
}
while(l <= r)
{
int mid = (l+r)/2;
if(check(mid))r = mid-1;
else l = mid+1;
}
return l;
}
