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