Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число.
За один ход робот может переместиться на одну клетку вправо, вверх, по диагонали вправо-вверх или по диагонали влево-ввверх.
Числа показывают расход энергии робота на прохождение клетки.
Определите максимальный расход энергии при переходе робота в правую верхнюю клетку поля и
количество клеток с нечётными числами, через которые робот проходит на пути с максимальным расходом энергии.
В ответе, через пробел, запишите два числа:
сначала максимальный расход энергии, затем – количество пройденных клеток с нечётными значениями.
Исходные данные записаны в электронной таблице.
Пример входных данных (для таблицы размером 4×4):
| 42 |
90 |
2 |
45 |
| 72 |
30 |
36 |
63 |
| 62 |
6 |
61 |
42 |
| 21 |
84 |
49 |
50 |
При указанных входных данных максимальный расход получится при движении по
маршруту 21 + 84 + 49 + 50 + 61 + 42 + 36 + 90 + 2 + 45 = 480.
При этом робот проходит через 5 клеток с нечётными числами (21, 49, 61, 45).
В ответе в данном случае надо записать числа 480 и 4.