// login-judger-enable-o2
#include <bits/stdc++.h>
#define N 1005
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
using namespace std;

char *p1, *p2, buf[1 << 14];
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 14), stdin), p1 == p2) ? EOF : *p1++)
template <typename T>
inline void read(T& x) {
	x = 0;
	register int t = 1;
	register int ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') t = -1;
		ch = getchar();
	}
	while ('0' <= ch && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	x *= t;
}
int n, m, k;
int a[N][N];
bool vis[N][N];

int main() {
	srand(time(0));  // 欧皇算法 
	read(n), read(m), read(k);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			read(a[i][j]);
		}
	}
	// 复杂度O(mnt) 
	// 由于1e9过不去，所以要保证mnt < 1e9 
	//int t = 1000000000 / (m * n);
	int t = 400005;  // 还是改定值吧 
	int res = INT_MAX;
	while (t--) {
		// 随机选取矩形的左上角 
		int x = rand() % (n - k + 1) + 1;
		int y = rand() % (m - k + 1) + 1;
		if (vis[x][y]) continue;
		vis[x][y] = 1;
		int minn = INT_MAX, maxn = -INT_MAX;
		for (int i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				minn = min(minn, a[x + i][y + j]);
				maxn = max(maxn, a[x + i][y + j]);
				if (maxn - minn > res) break;  
			}
			if (maxn - minn > res) break;
		}
		res = min(res, maxn - minn);
	}
	printf("%d", res);
	return 0;
}

本蒟蒻参考 @我没有名称 大佬写的随机化居然直接过了，这合理吗……