Задание выполняется с использованием прилагаемых файлов.
Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вниз или по диагонали вправо вниз. Шаг вправо разрешается сделать только в клетку с числом той же чётности, шаг вниз – только в клетку с числом другой чётности. Шаг по диагонали возможен всегда. Необходимо перевести робота в правую нижнюю клетку поля. Определите максимальную сумму чисел в клетках, через которые можно провести такой маршрут. Определите также количество клеток поля, в которые робот не сможет попасть из-за ограничений на возможные переходы.
В ответе, через пробел, запишите два числа: сначала максимально возможное значение суммы входящих в маршрут чисел, затем количество недоступных клеток.
Исходные данные записаны в электронной таблице. Пример входных данных (для таблицы размером 4×4):
При указанных входных данных максимальное значение 250 получится при движении по маршруту 53 → 63 → 62 → 59 → 13.
Недоступны для робота клетки с числами 18, 80, 2, 86 – всего 4 клетки. В ответе в данном случае надо записать числа 250 и 4.