CF1102F Elongated Matrix

给定一个 $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$-可接受遍历。

第一行包含两个整数 $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$），描述矩阵的内容。

输出一个整数 $k$，即存在某种行顺序使得遍历是 $k$-可接受遍历的最大值。

在第一个样例中，你可以将行重新排列如下，得到 $5$-可接受遍历： ``` 5 3 10 8 4 3 9 9 ``` 此时序列 $s$ 为 $[5, 10, 4, 9, 3, 8, 3, 9]$。任意相邻两个元素的差的绝对值至少为 $k=5$。 在第二个样例中，最大 $k=0$，任意顺序都是 $0$-可接受的。 在第三个样例中，原有顺序已经是 $3$-可接受的，可以保持不变。 由 ChatGPT 4.1 翻译