Задана матрица \(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\)-приемлемый обход.
Выходные данные
Выведите единственное целое число \(k\) — такое максимальное число, что существует порядок строк матрицы \(a\), который образует \(k\)-приемлемый обход.
Примечание
В первом примере можно переставить строки следующим образом, чтобы получить \(5\)-приемлемый обход:
5 3
10 8
4 3
9 9
Тогда последовательность \(s\) будет \([5, 10, 4, 9, 3, 8, 3, 9]\). Каждая пара соседних элементов отличается хотя бы на \(k = 5\).
Во втором примере максимальное \(k = 0\), любой порядок \(0\)-приемлем.
В третьем примере заданный порядок уже \(3\)-премлемый, можно его оставить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
9 9
10 8
5 3
4 3
|
5
|
|
2
|
2 4
1 2 3 4
10 3 7 3
|
0
|
|
3
|
6 1
3
6
2
5
1
4
|
3
|