#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
#define ll long long
//#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int x[3001][3001];
bool c(int k,int R,int C,int H,int W,int Q[3001][3001]){
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
x[i][j]=0;
}
}
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
x[i][j]=Q[i][j]<k;
if(Q[i][j]==k)x[i][j]+=100000000;
if(j>0)x[i][j]+=x[i][j-1];
}
}
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
if(i>0)x[i][j]+=x[i-1][j];
}
}
for(int i=H-1;i<R;i++){
for(int j=W-1;j<C;j++){
int z=x[i][j];
if(i>H-1)z-=x[i-H][j];
if(j>W-1)z-=x[i][j-W];
if(i>=H && j>=W)z+=x[i-H][j-W];
if(z>=(H*W/2)+100000000){
return 1;
}
}
}
return 0;
}
int rectangle(int R,int C,int H,int W,int Q[3001][3001]) {
int l=1,r=R*C+1;
while(l<r-1){
int m=(l+r)/2;
if(c(m,R,C,H,W,Q))r=m;
else l=m;
}
return l+1;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int R,C,H,W;
cin>>R>>C>>H>>W;
int Q[3001][3001];
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
cin>>Q[i][j];
}
}
cout<<rectangle(R,C,H,W,Q);
}
/*
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
*/
Compilation message
/tmp/ccipppzQ.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccUCGiAQ.o:quality.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
