source_code: import javafx.util.Pair;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.HashMap;
  
  public class ElongatedMatrix {
      private static int n;
      /**
       * if the rows are arranged in some permutation [p_1, p_2,...i,j,...p_n],
       * 1!=i!=j!=n, minCost[i][j] is the min k for any permutation with i&j adjacent
       **/
      private static int[][] minCost;
      /**
       * minCostEndpoints[i][j] is the min k for any permutation such that
       * the rows are arranged in some permutation [i, p_2, ... p_{n-1}, j],
       **/
      private static int[][] minCostEndpoints;
  
      /**
       * Max k of a path over a subset of all rows ending at a certain vertex
       * The first 16 bits of the key represent the subset. Node n is in the subset iff (x & (2 << n))!=0
       * key/(1<<16) is the end vertex number
       */
      private static HashMap<Integer, Integer> costs = new HashMap<>();
  
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int[] params = Arrays.stream(br.readLine().split(" "))
                  .mapToInt(x -> Integer.parseInt(x)).toArray();
          n = params[0];
          int m = params[1];
          int[][] matrix = new int[n][m];
          for (int i = 0; i < n; i++) {
              matrix[i] = Arrays.stream(br.readLine().split(" "))
                      .mapToInt(x -> Integer.parseInt(x)).toArray();
          }
          minCost = new int[n][n];
          minCostEndpoints = new int[n][n];
          for (int i = 0; i < n; i++) {
              for (int j = 0; j < n; j++) {
                  if (i > j) {
                      minCost[i][j] = Integer.MAX_VALUE;
                      for (int k = 0; k < m; k++) {
                          int diff = Math.abs(matrix[i][k] - matrix[j][k]);
                          if (diff < minCost[i][j]) {
                              minCost[i][j] = diff;
                          }
                      }
                      minCost[j][i] = minCost[i][j];
                  }
                  minCostEndpoints[i][j] = Integer.MAX_VALUE;
                  for (int k = 0; k < m - 1; k++) {
                      int diff = Math.abs(matrix[i][k + 1] - matrix[j][k]);
                      if (diff < minCostEndpoints[i][j]) {
                          minCostEndpoints[i][j] = diff;
                      }
                  }
              }
          }
          int maxCost = n == 1 ? minCostEndpoints[0][0] : 0;
          for (int i = 0; i < n; i++) {
              costs.clear();
              for (int j = 0; j < n; j++) {
                  if (i != j) {
                      int bitmask = (1 << i) | (1 << j);
                      int state = bitmask + (j << 16);
                      costs.put(state, minCost[i][j]);
                  }
              }
              for (int j = 0; j < n; j++) {
                  if (i != j) {
                      if (minCostEndpoints[i][j] <= maxCost) {
                          continue;
                      } else {
                          int pathCost = Math.min(minCostEndpoints[i][j], findMaxCost(i, j, (1 << n) - 1));
                          maxCost = Math.max(maxCost, pathCost);
                      }
                  }
              }
          }
          System.out.println(maxCost);
          br.close();
      }
  
      //find the minimum cost starting at st, ending at end, and using only the rows in set
      private static int findMaxCost(int st, int end, int set) {
          int state = set + (end << 16);
          if (costs.containsKey(state)) {
              return costs.get(state);
          }
          int maxCost = 0;
          for (int i = 0; i < n; i++) {
              if (i != st && i != end && (set & (1 << i)) != 0) {
                  int setWithoutEnd = set - (1 << end);
                  int pathCost = Math.min(findMaxCost(st, i, setWithoutEnd), minCost[i][end]);
                  maxCost = Math.max(pathCost, maxCost);
              }
          }
          costs.put(state, maxCost);
          return maxCost;
      }
  }
  