F. Вытянутая матрица
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана матрица $$$a$$$, состоящая из $$$n$$$ строк и $$$m$$$ столбцов. В каждой ячейке записано целое число.

Разрешается произвольно изменить порядок строк (в том числе и оставить начальный порядок), но не разрешается менять порядок ячеек в строке. После того, как был выбран некоторый порядок строк, матрица полностью обходится следующим образом: сначала посещаются все ячейки первого столбца с верхней строки до нижней, потом так же все ячейки второго столбца и так далее. Во время обхода выписывается последовательность чисел в ячейках в том же порядке, в котором они были посещены. Назовем эту последовательность $$$s_1, s_2, \dots, s_{nm}$$$.

Обход называется $$$k$$$-приемлемым, если для всех $$$i$$$ ($$$1 \le i \le nm - 1$$$) $$$|s_i - s_{i + 1}| \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$$$-приемлемый обход.

Примеры
Входные данные
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
Примечание

В первом примере можно переставить строки следующим образом, чтобы получить $$$5$$$-приемлемый обход:


5 3
10 8
4 3
9 9

Тогда последовательность $$$s$$$ будет $$$[5, 10, 4, 9, 3, 8, 3, 9]$$$. Каждая пара соседних элементов отличается хотя бы на $$$k = 5$$$.

Во втором примере максимальное $$$k = 0$$$, любой порядок $$$0$$$-приемлем.

В третьем примере заданный порядок уже $$$3$$$-премлемый, можно его оставить.