Elongated Matrix

给出一个矩阵$a$，由$n$行和$m$列组成。每个单元格中都包含一个整数。 你可以任意更改行的顺序(包括保留初始顺序)，但不能更改行中单元格的顺序。在选择了一些行的顺序后，你通过以下方式遍历整个矩阵：首先访问从上一行到下一行的第一列的所有单元格，然后访问第二列的所有单元格，依此类推。在遍历过程中，你可以按照访问它们的顺序记下单元格上的数字序列。假设该序列为$S_1$，$S_2$，……，$S_i$，……，$S_{NM}$。 如果所有|$s_i$−$s_{i+1}$|≥$k$（1≤$i$≤$nm$−1），则遍历$k$是可以被接受的。 请你求最大整数$k$，使得存在矩阵$a$的某一行的顺序中，$k$遍历可以被接受的。

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.

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.

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.

4 2
9 9
10 8
5 3
4 3

5

2 4
1 2 3 4
10 3 7 3

0

6 1
3
6
2
5
1
4

3

In the first example you can rearrange rows as following to get the $ 5 $ -acceptable traversal: ``` <br></br>5 3<br></br>10 8<br></br>4 3<br></br>9 9<br></br> ``` 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.