Злой гном закопал клад на клетчатом поле размера 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}). Строки соответствуют направлению сверху вниз, а столбцы — направлению слева направо. Все значения различны.

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