Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано натуральное число. За один ход робот может переместиться на одну клетку вправо или на одну клетку вниз. Выходить за пределы поля робот не может. Некоторые клетки на поле окружены границами, в эти клетки роботу заходить нельзя.
В начальный момент запас энергии робота составляет 3000 единиц. Проходя через каждую клетку, робот расходует энергию, при этом расход равен числу, записанному в клетке.
В клетках с выделенным фоном находятся зарядные станции.При прохождении через эти клетки робот не расходует, а пополняет запас энергии. Сумма пополнения равна числу, записанному в этой клетке.
Определите максимальный и минимальный запас энергии, который может быть у робота после перехода в правую нижнюю клетку поля. В ответе запишите два числа: сначала максимально возможное значение, затем – минимальное.
Исходные данные записаны в
электронной таблице. Границы отмечены утолщёнными линиями.
Пример входных данных (для таблицы размером 4×4):
.png)
При указанных входных данных максимальное значение получается при движении по маршруту 3000 – 13 – 8 + 35 – 57 – 17 – 32 – 43 = 2865, а минимальное – при движении по маршруту 3000 – 13 – 30 – 32 – 90 – 12 – 80 – 43 = 2700.
Ответ запишите в виде двух чисел, разделенных одним пробелом.