Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого лежит монета достоинством от 1 до 100. За один ход Робот может переместиться на одну клетку вправо, вниз или по диагонали вправо вниз.
Шаг вправо разрешается сделать только в клетку, где лежит монета с достоинством той же чётности, шаг вниз – только в клетку с монетой другой чётности. Шаг по диагонали возможен всегда. Необходимо перевести Робота в правую нижнюю клетку поля.
Определите максимальную денежную сумму, которую может собрать Робот, и количество клеток поля, недоступных для Робота.
Пример входных данных:
| 35 |
29 |
40 |
66 |
| 10 |
50 |
74 |
48 |
| 87 |
33 |
24 |
17 |
| 13 |
94 |
23 |
35 |
Оптимальный маршрут проходит через клетки с монетами достоинством 35, 10, 87, 33, 23, 35 (сумма 223). Клетки с монетами достоинством 13, 40 и 66 недоступны для Робота из-за ограничений.
Исходные данные записаны в файле в виде электронной таблице, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа: максимальную денежную сумму, которую может собрать Робот, затем количество клеток поля, недоступных Роботу.