#include "quality.h"
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int N1 = 3005;
ll ar[N1+4][N1+4],p[N1+4][N1+4];
int n,m,rr,c;
bool ch(ll x){
for(int i=1;i<=n;i++)p[i][0]=0;
for(int i=1;i<=m;i++)p[0][i]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
p[i][j]=0;
if(ar[i][j]>x)p[i][j]=1;
p[i][j]+=p[i-1][j]+p[i][j-1]-p[i-1][j-1];
if(i<rr||j<c)continue;
ll va=p[i][j]-p[i-rr][j]-p[i][j-c]+p[i-rr][j-c];
// cout<<va<<endl;
if(va<=(rr*c)/2)return 1;
}
}
return 0;
}
int sol(){
ll l=1,r=n*m,ans=-1;
while(l<=r){
ll mid=l+(r-l)/2;
if(ch(mid)){
r=mid-1;
ans=mid;
}
else l=mid+1;
}
return ans;
}
int rectangle(int N,int M,int R,int C,int Q[3001][3001]){
n=N;m=M;rr=R;c=C;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ar[i][j]=Q[i-1][j-1];
}
}
return sol();
}
//int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cin>>n>>m>>rr>>c;
//
//
// return 0;
//}
/*
5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
*/
