410210: GYM103984 F Парад во время чумы

F. Парад во время чумыограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

В далекой стране Байтландии сегодня проходит парад. Военные машины уже проехали по городу, самолёты уже пролетели, остался лишь марш солдат, который вам и предстоит организовать в кратчайшие сроки.

Всего в марше должны были участвовать $$$n$$$ отрядов солдат, по $$$m$$$ солдат в каждом. К сожалению, собираться большим числом людей в наши времена крайне сложно, и вы решили, что хотите выбрать из $$$n$$$ отрядов по одному представителю и пройти одной большой шеренгой длины $$$n$$$. Выбранные солдаты будут расположены в шеренге в порядке возрастания номеров их отрядов.

Ваше начальство хочет, чтобы строй был максимально ровным из возможных. Неровность шеренги определяется максимальным модулем разности роста соседних солдат.

Время поджимает — выходить уже через 5 часов! Определите, какой минимальной неровности шеренги можно добиться при таких условиях.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le nm \le 10^6$$$) — количество отрядов и число солдат в каждом из них.

В следующих $$$n$$$ строках находится по $$$m$$$ целых чисел $$$a_{i, j}$$$ ($$$10^6 \leq a_{i, j} \leq 2 \cdot 10^6$$$) — высота в микрометрах $$$j$$$-го солдата $$$i$$$-го отряда.

Выходные данные

Выведите одно число — минимальную возможную неровность шеренги в микрометрах.

ПримерВходные данные

3 4
1830000 1790000 1810000 1820000
1730000 1690000 1750000 1760000
1910000 1850000 1800000 1710000

Выходные данные

40000

Примечание

В тесте из условия одним из оптимальных вариантов будет шеренга из солдат с ростами: 179 см, 176 см, 180 см. Модуль разности роста первого и второго солдатов составляет 3 см, а второго и третьего — 4. Таким образом, неровность шеренги равна 4 см или 40000 микрометров.