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