ТПУ: основной тур

Соревнование завершилось 15.04.18 в 16:00

F. Злой гном

Ограничение по времени: 1 с.
Ограничение по памяти: 256 МБ

Злой гном закопал клад на клетчатом поле размера n \times n. Гном пронумеровал случайным образом все клетки целыми последовательными числами от 1 до n^{2} так, что каждая клетка имеет уникальный номер. Злой гном проболтался, что клад закопан в одной из клеток поля. Более того, глубина, на которой закопан клад в этой клетке в точности равна присвоенному этой клетке номеру.

Паша хочет выкопать клад. Для этого у Паши имеется карта поля, содержащая нумерацию клеток, заданную гномом. Изначально Паша находится в левом верхнем углу поля. Злой гном не разрешил Паше сколько угодно ходить по клеткам поля во всех направлениях, поэтому Паша может перемещаться по полю только по вертикали и горизонтали. При этом можно переместиться на одну клетку в вертикальном или горизонтальном направлении за одну единицу времени. Чтобы выкопать яму глубины d, Паша тратит d единиц времени. Паша копает ямы только той глубины, которая равна номеру клетки, на которой он стоит. При выкапывании ямы определённой глубины в одной из клеток может произойти одно из трёх событий:

  • Паша находит клад;

  • Паша не находит клад, а гном подсказывает, что клад находится в клетке с большим номером;

  • Паша не находит клад, а гном подсказывает, что клад находится в клетке с меньшим номером.

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

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

Первая строка входных данных содержит одно целое число n — длину стороны поля гнома (1 \leqslant n \leqslant 20).

Далее следует n строк по n целых чисел a_{i, j} — нумерация клеток поля, заданная гномом (1 \leqslant a_{i, j} \leqslant n^{2}). Строки соответствуют направлению сверху вниз, а столбцы — направлению слева направо. Все значения различны.

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

В единственной строке выходных данных необходимо вывести одно целое число — искомое минимальное время.

Примеры
Стандартный вводСтандартный вывод
2
1 3
4 2
10
3
2 7 4
9 5 1
8 3 6
28