#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
const int NN=3e3;
int pref[NN+10][NN+10];
int read_p(int x,int y)
{
if(x<0 || y<0)
return 0;
return pref[x][y];
}
void count_pref(int R,int C,int Q[3001][3001],int c)
{
for(int i=0;i<R;i++)
{
for(int j=0;j<C;j++)
pref[i][j]=read_p(i-1,j)+read_p(i,j-1)-read_p(i-1,j-1)+(Q[i][j]>c);
}
return;
}
int min_rec(int R,int C,int H,int W)
{
int ans=R*C;
for(int i=H-1;i<R;i++)
{
for(int j=W-1;j<C;j++)
ans=min(ans,read_p(i,j)-read_p(i-H,j)-read_p(i,j-W)+read_p(i-H,j-W));
}
return ans;
}
int rectangle(int R,int C,int H,int W,int Q[3001][3001])
{
int bg=1,en=R*C;
while(bg<en)
{
int mid=(bg+en)/2;
count_pref(R,C,Q,mid);
if(min_rec(R,C,H,W)>=(H*W+1)/2)
bg=mid+1;
else
en=mid;
}
return bg;
}
