#include <bits/stdc++.h>
using namespace std;
#include "quality.h"
const int N=3004;
int n,m,h,w,x,a[N][N],pr[N][N];
int cmp(int br){
return (br==x?0:br>x?-1:1);
}
bool chk(){
pr[0][0]=cmp(a[0][0]);
for(int i=1;i<n;++i)
pr[i][0]=pr[i-1][0]+cmp(a[i][0]);
for(int i=1;i<m;++i)
pr[0][i]=pr[0][i-1]+cmp(a[0][i]);
for (int i=1;i<n;++i) {
for (int j=1;j<m;++j)
pr[i][j]=pr[i-1][j]+pr[i][j-1]
-pr[i-1][j-1]+cmp(a[i][j]);
}
for(int i=0;i+h<n;++i){
for(int j=0;j+w<m;++j){
int lg=(!i||!j?0:pr[i-1][j-1]);
int dg=(!i?0:pr[i-1][j+w]);
int dl=(!j?0:pr[i+h][j-1]);
int dd=(pr[i+h][j+w]);
int s=(dd-dl-dg+lg);
if(s>=0)
return 1;
}
}
return 0;
}
int rectangle(int R,int C,int H,int W,int Q[3001][3001]){
n=R,m=C,h=H-1,w=W-1;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
a[i][j]=Q[i][j];
int l=1,r=n*m,ans=r;
while(l<=r){
x=(l+r)/2;
if(chk()){
ans=x;
r=x-1;
}else
l=x+1;
}
return ans;
}
