#include "quality.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int l=0;
int r=R*C;
int mid;
int best=r;
while(l<=r){
mid=(l+r)/2;
int arr[R+5][C+5];
int dp[R+5][C+5];
memset(dp,0,sizeof(dp));
//show(mid,mid);
for(int x=1;x<=R;x++){
for(int y=1;y<=C;y++){
arr[x][y]=(Q[x-1][y-1]<=mid);
dp[x][y]=dp[x-1][y]+dp[x][y-1]-dp[x-1][y-1]+arr[x][y];
//cout << arr[x][y] << " ";
}
//cout << "\n";
}
int maxi=0;
for(int x=H;x<=R;x++){
for(int y=W;y<=C;y++){
maxi=max(maxi,dp[x][y]-dp[x][y-W]-dp[x-H][y]+dp[x-H][y-W]);
}
}
if(maxi>H*W/2){
best=mid;
r=mid-1;
}
else l=mid+1;
}
return best;
}
