CF1102F.Elongated Matrix

You are given a matrix $a$, consisting of $n$ rows and $m$ columns. Each cell contains an integer in it.

You can change the order of rows arbitrarily (including leaving the initial order), but you can't change the order of cells in a row. After you pick some order of rows, you traverse the whole matrix the following way: firstly visit all cells of the first column from the top row to the bottom one, then the same for the second column and so on. During the traversal you write down the sequence of the numbers on the cells in the same order you visited them. Let that sequence be $s_1, s_2, \dots, s_{nm}$.

The traversal is $k$-acceptable if for all $i$ ($1 \le i \le nm - 1$) $|s_i - s_{i + 1}| \ge k$.

Find the maximum integer $k$ such that there exists some order of rows of matrix $a$ that it produces a $k$-acceptable traversal.

给你一个由 $n$ 行 $m$ 列组成的矩阵 $a$，其中每个单元格包含一个整数。

你可以任意改变行的顺序（包括保持初始顺序不变），但不能改变每行内部各单元格的顺序。选定某种行顺序后，你按如下方式遍历整个矩阵：首先从上到下访问第一列的所有单元格，然后同样地依次访问第二列、第三列……直到最后一列。在遍历过程中，你按访问顺序将各单元格中的数字依次记录下来，得到序列 $s_1, s_2, \dots, s_{nm}$。

若对所有 $i$（$1 \le i \le nm - 1$）均满足 $|s_i - s_{i + 1}| \ge k$，则称该遍历是 $k$-可接受的。

请找出最大的整数 $k$，使得存在矩阵 $a$ 的某种行排列，使其产生的遍历是 $k$-可接受的。

The first line contains two integers $n$ and $m$ ($1 \le n \le 16$, $1 \le m \le 10^4$, $2 \le nm$) — the number of rows and the number of columns, respectively.

Each of the next $n$ lines contains $m$ integers ($1 \le a_{i, j} \le 10^9$) — the description of the matrix.

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 16$，$1 \le m \le 10^4$，$2 \le nm$），分别表示矩阵的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个整数（$1 \le a_{i, j} \le 10^9$），表示该矩阵。

Print a single integer $k$ — the maximum number such that there exists some order of rows of matrix $a$ that it produces an $k$-acceptable traversal.

输出一个整数 $k$ —— 满足存在矩阵 $a$ 的某一行排列顺序，使得该排列能产生一个 $k$-可接受遍历的最大 $k$ 值。

In the first example you can rearrange rows as following to get the $5$-acceptable traversal:

5 3
10 8
4 3
9 9

Then the sequence $s$ will be $[5, 10, 4, 9, 3, 8, 3, 9]$. Each pair of neighbouring elements have at least $k = 5$ difference between them.

In the second example the maximum $k = 0$, any order is $0$-acceptable.

In the third example the given order is already $3$-acceptable, you can leave it as it is.

在第一个例子中，你可以将行重新排列如下，从而得到一个 $5$-可接受的遍历：

5 3
10 8
4 3
9 9

此时序列 $s$ 将为 $[5, 10, 4, 9, 3, 8, 3, 9]$。其中每一对相邻元素之间的差值至少为 $k = 5$。

在第二个例子中，最大的 $k = 0$，任意顺序都是 $0$-可接受的。

在第三个例子中，给定的顺序本身已是 $3$-可接受的，因此你可以保持原样不变。