#include<bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
//#include "quality.h"
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define endl "\n"
#define MAXN 9000000
static int R,C,H,W,Q[3001][3001],i,j,ans;
int pref[3010][3010], q[3010][3010], pom[3010][3010];
//int bit[310];
int pola;
/*pair<int, int> pos[90010];
ll sum(int x)
{
ll ret=0;
while (x)
{
ret+=bit[x];
x-=x&(-x);
}
return ret;
}
void upd(int x, int val)
{
while (x<MAXN)
{
bit[x]+=val;
x+=x&(-x);
}
return;
}*/
bool check(int med)
{
for (int i=0; i<R; i++)
{
for (int j=0; j<C; j++)
{
pref[i][j]=0;
pom[i][j]=(q[i][j]<=med) ? 1 : 0;
///cout<<pom[i][j]<<" ";
}
///cout<<endl;
}
///cout<<endl;
for (int i=0; i<R; i++)
{
for (int j=0; j<C; j++)
{
pref[i][j]=pom[i][j];
if (i>0) pref[i][j]+=pref[i-1][j];
if (j>0) pref[i][j]+=pref[i][j-1];
if (i>0 && j>0) pref[i][j]-=pref[i-1][j-1];
///cout<<pref[i][j]<<" ";
}
///cout<<endl;
}
for (int i=H-1; i<R; i++)
{
for (int j=W-1; j<C; j++)
{
int koliko=pref[i][j];
if (i>=H) koliko-=pref[i-H][j];
if (j>=W) koliko-=pref[i][j-W];
if (i>=H && j>=W) koliko+=pref[i-H][j-W];
if (koliko>=pola) { /*cout<<med<<" "<<i<<" "<<j<<" "<<koliko<<endl;*/ return true; }
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
pola=H*W/2+1;
for (int i=0; i<R; i++) for (int j=0; j<C; j++) q[i][j]=Q[i][j];
int l=1, r=R*C;
ll ress=-1;
while (l<=r)
{
int mid=l+(r-l)/2;
///cout<<mid<<":"<<endl<<endl<<endl;
if (check(mid))
{
ress=mid;
r=mid-1;
}
else l=mid+1;
}
return ress;
/*int ress=R*C+1;
int koji=H*W/2+1;
for (int i=0; i<R; i++) for (int j=0; j<C; j++) pos[Q[i][j]]={i, j};
for (int i=0; i<=R-H; i++)
{
for (int k=i; k<i+H; k++)
for (int j=0; j<W; j++)
{ cout<<Q[k][j]<<" "; upd(Q[k][j], 1); }
cout<<endl;
for (int j=0; j<=C-W; j++)
{
int l=1, r=R*C;
int trRess=1000000000;
while (l<=r)
{
int mid=l+(r-l)/2;
if (sum(mid)>=koji)
{
trRess=mid;
r=mid-1;
}
else l=mid+1;
}
cout<<"ee "<<trRess<<endl;
ress=min(trRess, ress);
for (int k=i; k<i+H; k++)
{
upd(Q[k][j], -1);
if (j+W<C) upd(Q[k][j+W], 1);
}
}
}
return ress;*/
//return 1;
}
int main(){
scanf("%d%d%d%d",&R,&C,&H,&W);
for (i=0;i<R;i++) for (j=0;j<C;j++) scanf("%d",&Q[i][j]);
ans = rectangle(R,C,H,W,Q);
printf("%d\n",ans);
return 0;
}
/*for (int j=0; j<=C-W; j++)
{
int koliko=0;
for (int k=1; k<=R*C; k++)
{
if (pos[k].xx>=i && pos[k].xx<i+H && pos[k].yy>=j && pos[k].yy<j+W) koliko++;
if (koliko==koji)
{
//cout<<i<<" "<<j<<" "<<k<<endl;
ress=min(ress, k);
break;
}
}
vector<int> koji;
for (int x=i; x<i+H; x++)
{
for (int y=j; y<j+W; y++)
koji.pb(Q[x][y]);
}
sort(koji.begin(), koji.end());
//cout<<i<<" "<<j<<" "<<koji[koji.size()/2]<<endl;
ress=min(ress, koji[koji.size()/2]);
}*/
Compilation message
quality.cpp: In function 'int main()':
quality.cpp:144:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
144 | scanf("%d%d%d%d",&R,&C,&H,&W);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
quality.cpp:145:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
145 | for (i=0;i<R;i++) for (j=0;j<C;j++) scanf("%d",&Q[i][j]);
| ~~~~~^~~~~~~~~~~~~~~
/tmp/ccwfHoEV.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccHQEF10.o:quality.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
