Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо или на одну клетку вверх. Некоторые клетки выделены тёмным фоном. В эти клетки роботу заходить нельзя. Клетка, из которой робот не может сделать допустимого хода (справа и сверху находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток. В начальный момент робот обладает запасом энергии, которая расходуется на движение по клеткам. Расход энергии на прохождение каждой клетки, включая стартовую и финальную, равен числу, записанному в этой клетке.
Задание 1. Определите минимальный начальный запас энергии, который позволит роботу добраться до какой-нибудь финальной клетки.
Задание 2. Определите минимальный начальный запас энергии, который позволит роботу добраться до любой финальной клетки.
В обоих заданиях энергии должно хватить и на прохождение финальной клетки.
Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на задание 1, затем ответ на задание 2.
Файл