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