Квадрат разлинован на N×N клеток (< N < ). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от до . Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Между соседними клетками квадрата могут быть внутренние стены. Сквозь стену Робот пройти не может.

Откройте файл. Определите максимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите только одно число – искомую сумму.