Задача №114708. Парад во время чумы
В далекой стране Байтландии сегодня проходит парад. Военные машины уже проехали по городу, самолёты уже пролетели, остался лишь марш солдат, который вам и предстоит организовать в кратчайшие сроки.
Всего в марше должны были участвовать \(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\)-го отряда.
Выведите одно число — минимальную возможную неровность шеренги в микрометрах.
В тесте из условия одним из оптимальных вариантов будет шеренга из солдат с ростами: 179 см, 176 см, 180 см. Модуль разности роста первого и второго солдатов составляет 3 см, а второго и третьего — 4. Таким образом, неровность шеренги равна 4 см или 40000 микрометров.
3 4 1830000 1790000 1810000 1820000 1730000 1690000 1750000 1760000 1910000 1850000 1800000 1710000
40000