给定一个矩阵 $$$a$$$,由 $$$n$$$ 行和 $$$m$$$ 列组成。每个单元格中都包含一个整数。
您可以任意更改行的顺序(包括保留初始顺序),但不能更改行中单元格的顺序。选择某种行顺序后,按以下方式遍历整个矩阵:首先从顶行到底行访问第一列的所有单元格,然后访问第二列,依此类推。在遍历过程中,您按照访问单元格的顺序记下单元格上的数字序列。令该序列为 $$$s_1, s_2, \dots, s_{nm}$$$。
如果对于所有 $$$i$$$ ($$$1 \le i \le nm - 1$$$) $$$|s_i - s_{i + 1}| ,则遍历是 $$$k$$$ 可接受的\ge 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$$$ — 矩阵 $$$a$$$ 中存在某种行顺序的最大数量,它会产生 $$$k$$$ 可接受的遍历。
示例
输入 #1
4 2 9 9 10 8 5 3 4 3
输出 #1
5
输入 #2
2 4 1 2 3 4 10 3 7 3
输出 #2
0
输入 #3
6 1 3 6 2 5 1 4
输出 #3
3
注意
在第一个示例中,您可以按如下方式重新排列行以获得 $$$5$$$ 可接受的遍历:
那么序列 $$$s$$$ 将是 $$$[5, 10, 4, 9, 3, 8, 3, 9]$$$。每对相邻元素之间至少有 $$$k = 5$$$ 差异。
在第二个示例中,最大值 $$$k = 0$$$,任何订单都是 $$$0$$$ 可接受的。
在第三个示例中,给定的订单已经 $$$3$$$ 可以接受,您可以保持原样。