#include "quality.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 3010;
int sum[N];
int sump = 0;
int pi=0, pj=0;
int n, m, h, w;
bool marked[N][N];
pii pos[N*N];
bool mv()
{
while (sump > h*w/2) {
if (pi+h < n) {
sump -= sum[pi];
sump += sum[pi+h];
++pi;
} else if (pj+w < m) {
Loop (i,0,n) {
sum[i] -= marked[i][pj];
sum[i] += marked[i][pj+w];
}
pi = 0;
pj = pj+1;
sump = 0;
Loop (i,0,h)
sump += sum[i];
} else {
return 0;
}
}
return 1;
}
void mark(int i, int j)
{
if (pi <= i && i < pi+h && pj <= j && j < pj+w)
sump++;
if (pj <= j && j < pj+w)
sum[i]++;
marked[i][j] = 1;
}
int rectangle(int _R, int _C, int _H, int _W, int Q[3001][3001])
{
n = _R; m = _C; h = _H; w = _W;
Loop (i,0,n) Loop (j,0,m)
pos[Q[i][j]-1] = {i, j};
LoopR (x,0,n*m) {
mark(pos[x].first, pos[x].second);
if (!mv())
return x+1;
}
return -1;
}
