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.


-----Input-----

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.


-----Output-----

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.


-----Examples-----
Input
4 2
9 9
10 8
5 3
4 3

Output
5

Input
2 4
1 2 3 4
10 3 7 3

Output
0

Input
6 1
3
6
2
5
1
4

Output
3



-----Note-----

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.

Source: codeforces | Difficulty: HARD
Tags: Bit manipulation

Graph algorithms

Sorting

Complete search

Dynamic programming


Solutions:
import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def solve(i, n, delta, delta2):
	inf = 2 * 10 ** 9
	dp = [[-1] * n for _ in range(1 << n)]
	dp[1 << i][i] = inf
	stack = [(1 << i, i)]
	for t in range(1, n + 1):
		next_s = []
		for (bit, v) in stack:
			for dest in range(n):
				if 1 << dest & bit:
					continue
				if dp[bit | 1 << dest][dest] == -1:
					next_s.append((bit | 1 << dest, dest))
				dp[bit | 1 << dest][dest] = max(dp[bit | 1 << dest][dest], min(dp[bit][v], delta[v][dest]))
		stack = next_s
	return max((min(delta2[j][i], dp[-1][j]) for j in range(n) if i != j))

def main():
	(n, m) = map(int, input().split())
	matrix = [tuple(map(int, input().split())) for _ in range(n)]
	if n == 1:
		print(min((abs(x - y) for (x, y) in zip(matrix[0], matrix[0][1:]))))
		exit()
	delta = [[0] * n for _ in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			delta[i][j] = delta[j][i] = min((abs(x - y) for (x, y) in zip(matrix[i], matrix[j])))
	delta2 = [[0] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			delta2[i][j] = min((abs(x - y) for (x, y) in zip(matrix[i], matrix[j][1:])), default=2 * 10 ** 9)
	print(max((solve(i, n, delta, delta2) for i in range(n))))
main()


import sys
import copy
input = sys.stdin.readline
(n, m) = map(int, input().split())
MAT = [list(map(int, input().split())) for i in range(n)]
if n == 1:
	ANS = 10 ** 10
	for i in range(1, m):
		if ANS > abs(MAT[0][i] - MAT[0][i - 1]):
			ANS = abs(MAT[0][i] - MAT[0][i - 1])
	print(ANS)
	sys.exit()
EDGE0 = [[10 ** 10] * n for i in range(n)]
EDGE1 = [[10 ** 10] * n for i in range(n)]
MAX = 0
MIN = 0
if m != 1:
	for i in range(n):
		for j in range(n):
			EDGE1[i][j] = EDGE1[j][i] = min([abs(MAT[i][k] - MAT[j][k]) for k in range(m)])
			if EDGE1[i][j] > MAX:
				MAX = EDGE1[i][j]
			EDGE0[i][j] = min([abs(MAT[i][k] - MAT[j][k - 1]) for k in range(1, m)])
else:
	for i in range(n):
		for j in range(n):
			EDGE1[i][j] = EDGE1[j][i] = min([abs(MAT[i][k] - MAT[j][k]) for k in range(m)])
			if EDGE1[i][j] > MAX:
				MAX = EDGE1[i][j]

def Hamilton(start, USED, rest, last, weight):
	if MEMO[last * (1 << n) + USED] != 2:
		return MEMO[last * (1 << n) + USED]
	if rest == 1:
		for i in range(n):
			if USED & 1 << i == 0:
				final = i
				break
		if EDGE0[start][final] >= weight and EDGE1[last][final] >= weight:
			MEMO[last * (1 << n) + USED] = 1
			return 1
		else:
			MEMO[last * (1 << n) + USED] = 0
			return 0
	for j in range(n):
		if USED & 1 << j == 0 and EDGE1[last][j] >= weight:
			NEXT = USED + (1 << j)
			if Hamilton(start, NEXT, rest - 1, j, weight) == 1:
				MEMO[last * (1 << n) + USED] = 1
				return 1
	else:
		MEMO[last * (1 << n) + USED] = 0
		return 0
while MAX != MIN:
	aveweight = (MAX + MIN + 1) // 2
	for start in range(n):
		MEMO = [2] * (n * 1 << n + 1)
		START = 1 << start
		if Hamilton(start, START, n - 1, start, aveweight) == 1:
			MIN = aveweight
			break
	else:
		MAX = aveweight - 1
print(MAX)


import sys

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
(N, M) = reads()
table = [reads() for i in range(N)]
A = [[0] * N for i in range(N)]
B = [[0] * N for i in range(N)]
for i in range(N):
	for j in range(N):
		res = 10 ** 9 + 7
		for k in range(M):
			res = min(res, abs(table[i][k] - table[j][k]))
		A[i][j] = res
		A[j][i] = res
		res = 10 ** 9 + 7
		for k in range(M - 1):
			res = min(res, abs(table[i][k] - table[j][k + 1]))
		B[i][j] = res
dp = [[-1] * N for i in range(1 << N)]

def calc(mask, v):
	if dp[mask][v] != -1:
		return dp[mask][v]
	res = 0
	for u in range(N):
		if mask & 1 << u and u != v:
			res = max(res, min(calc(mask ^ 1 << v, u), A[u][v]))
	dp[mask][v] = res
	return dp[mask][v]
ans = 0
for i in range(N):
	dp = [[-1] * N for i in range(1 << N)]
	for k in range(N):
		if k == i:
			dp[1 << k][k] = 10 ** 9 + 7
		else:
			dp[1 << k][k] = 0
	for j in range(N):
		ans = max(ans, min(B[j][i], calc((1 << N) - 1, j)))
print(ans)