№187147463

Квадрат разлинован на N×N клеток (3 < N < 17). В каждой клетке лежат конфеты, количество которых соответствует записанному числу. На поле работает исполнитель Дружище, который съедает все конфеты в клетке. Также, если исполнитель проходит между двумя четными или двумя нечетными значениями, то Добрый Волшебник дает ему еще 10 конфет, которые он, конечно же, сразу съедает. Так, например, если исполнитель приходит в клетку С3 из клетки В3, считается, что он прошел между клетками С2 и С4, если в С3 из С2 - между В3 и D3. Исполнитель может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Дружище перемещается в соседнюю правую клетку, по команде вниз - в соседнюю нижнюю. При попытке выхода за границу квадрата Дружище расстраивается, что ему не дают конфеты, и отказывается идти дальше.

Нам важно, чтобы Дружище съел как можно меньше конфет и при этом добрался из левой верхней клетки в правую нижнюю.

Исходные данные представляют собой электронную таблицу в файле 18-J5 размером N×N, каждая ячейка которой соответствует клетке квадрата.

Пример входных данных:

Для указанных входных данных ответом должно быть число - минимально возможное съедаемое количество конфет - 53.