Одно из полей Фермера Джона весьма холмисто. И он хочет купить новый трактор для работы на этом поле. Поле описывается решеткой из N x N (1 <= N <= 500) неотрицательных целых высот ячеек. Трактор может перемещаться из ячейки в соседнюю (на один шаг на север, юг, запад или восток), с разницей их высот D ровно за D единиц денег.
ФД хочет заплатить достаточно, так чтобы его трактор, начиная с некоторой ячейки поля мог посетить как минимум половину ячеек поля. Если число ячеек в поле - нечетное, то половина, округленная вверх.
Определите минимальную стоимость покупки трактора способного выполнить эту задачу. PROBLEM NAME: tractor
Формат входных данных
* Строка 1: Значение N.
* Строки 2..1+N: Каждая строка содержит N разделенных одиночными пробелами неотрицательных целых чисел (каждое не более миллиона), определяющих строку поля ФД.
Формат выходных данных
* Line 1: Минимальная стоимость трактора, который способен объехать не менее половины этого поля.
Примечание
Трактор стоимостью 3 способен перемещаться из ячейки с высотой 0 в ячейку с высотой 3. Поэтому он может посетить все ячейки с высотами 0 и 3. Вместе они представляют не менее половины фермы.