Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вверх, по диагонали вправо-вверх или по диагонали влево-вверх. Числа показывают расход энергии робота на прохождение клетки.
Определите минимальный расход энергии при переходе робота в правую верхнюю клетку поля и количество клеток с нечётными числами, через которые робот проходит на пути с минимальным расходом энергии.
Пример входных данных (для таблицы размером 4×4):
При указанных входных данных минимальный расход получится при движении по маршруту 51 + 39 + 11 + 2 + 56 = 159. При этом робот проходит через 3 клетки с нечётными числами (51, 39, 11). В ответе в данном случае надо записать числа 159 и 3.
Исходные данные записаны в файле 18-156.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. В ответе запишите два числа: сначала минимальный расход энергии, затем – количество пройденных клеток с нечётными значениями.