1zhengfangxing

// Problem: 理想的正方形
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/1093/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq

include <bits/stdc++.h>

//#define int long long

define help

define pb push_back

define fi first

define se second

define mkp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}

const int N=1005;
int n,m,k,a[N][N];
int row_min[N][N],row_max[N][N],mx[N],mn[N],tmp[N];
int q[N],hh,tt;
void get_min(int a[],int b[],int n)
{
hh=tt=0;
for(int i=1;i<=n;i++)
{
while(hh<=tt&&i-q[hh]+1>k)hh++;
while(hh<=tt&&a[q[tt]]>=a[i])tt--;
q[++tt]=i;
b[i]=a[q[hh]];
}
}
void get_max(int a[],int b[],int n)
{
hh=tt=0;
for(int i=1;i<=n;i++)
{
while(hh<=tt&&i-q[hh]+1>k)hh++;
while(hh<=tt&&a[q[tt]]<=a[i])tt--;
q[++tt]=i;
b[i]=a[q[hh]];
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)get_min(a[i],row_min[i],m),get_max(a[i],row_max[i],m);
int res=1e9;
for(int j=k;j<=m;j++)
{
for(int i=1;i<=n;i++)tmp[i]=row_min[i][j];
get_min(tmp,mn,n);
for(int i=1;i<=n;i++)tmp[i]=row_max[i][j];
get_max(tmp,mx,n);
for(int i=k;i<=n;i++)res=min(res,mx[i]-mn[i]);
}
printf("%d",res);
return 0;
}