← 返回题目列表

Codeforces · 1102/F

F. 拉长矩阵

中文机器翻译题面 查看原题

给定一个矩阵 $$$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$$$ 可以接受,您可以保持原样。