Квадрат разлинован на 22 × 22 клеток. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены; они обозначены в файле утолщёнными линиями. Сквозь стену Робот пройти не может.
В каждой клетке квадрата записано натуральное число. При каждом перемещении Робот расходует энергию: по команде вправо — столько единиц, сколько записано в клетке, в которую он переходит, по команде вниз — вдвое больше. В стартовой клетке энергия не расходуется.
Исходные данные приведены в файле электронной таблицы.
Файл варианта: 18-{2}.ods
В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, — Робот не может продолжать движение, поэтому маршрут на них заканчивается. Определите максимальный и минимальный суммарный расход энергии на маршруте из левой верхней клетки в конечную клетку маршрута.
Формат ответа: два числа через пробел — сначала максимальное значение, затем минимальное. Например: 4271 1350