#include <bits/stdc++.h>
using namespace std;
int g[20][20], mp[20][10005];
int g2[20][20];
int dp[1 << 17][17];
int ct[1 << 17];
int Hamiltonpath(int g[][20], int g2[][20], int n, int beginwith) {
  int up = 1 << n;
  for (int i = 0; i < n; i++) ct[1 << i] = i;
  for (int i = 0; i < up; i++) {
    for (int j = 0; j < n; j++) {
      dp[i][j] = 0;
    }
  }
  dp[1 << beginwith][beginwith] = 1e9;
  for (int i = 0; i < up; i++) {
    for (int j = i; j; j &= j - 1) {
      int end = ct[j & -j];
      for (int no = ((1 << n) - 1) ^ i; no; no &= no - 1) {
        int nex = ct[no & -no];
        dp[i | (no & -no)][nex] =
            max(dp[i | (no & -no)][nex], min(dp[i][end], g[end][nex]));
      }
    }
  }
  int ret = 0;
  for (int i = 0; i < n; i++)
    ret = max(ret, min(dp[up - 1][i], g2[i][beginwith]));
  return ret;
}
int solve(int g[][20], int g2[][20], int n) {
  int ret = 0;
  for (int beginwith = 0; beginwith < n; beginwith++) {
    ret = max(ret, Hamiltonpath(g, g2, n, beginwith));
  }
  return ret;
}
int main() {
  int n, m;
  while (~scanf("%d%d", &n, &m)) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        scanf("%d", &mp[i][j]);
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        g[i][j] = g2[i][j] = 1e9;
        for (int k = 0; k < m; k++)
          g[i][j] = min(g[i][j], abs(mp[i][k] - mp[j][k]));
        for (int k = 0; k + 1 < m; k++)
          g2[i][j] = min(g2[i][j], abs(mp[i][k] - mp[j][k + 1]));
      }
    }
    printf("%d\n", solve(g, g2, n));
  }
}
