№287952912

Виртуальный исполнитель Варя живёт на клеточном поле размером N×M клеток. Исполнитель может перемещаться по клеткам, выполняя за одно перемещение одну из трёх команд: вправо, вниз или телепорт. По команде вправо Варя перемещается в соседнюю правую клетку, по команде вниз - в соседнюю нижнюю, по команде телепорт - в любую клетку ниже и/или правее той, в которой находится, кроме двух соседних клеток (т.е. исполнитель предпочитает команды вниз и вправо, если нужно перейти в соседнюю клетку).

Поле ограничено внешними стенами, за которые Варя никогда не выходит. В каждой клетке поля записано целое число, не превышающее по модулю 100. Исполнитель суммирует числа в клетках, которые посетил.

Определите минимальную сумму, которую может получить Варя, а также сколько раз ей пришлось воспользоваться командой телепорт, чтобы получить эту сумму. Исходные данные записаны в файле в виде электронной таблице размером N×M, каждая ячейка которой соответствует клетке поля. Внешние стены обозначены утолщёнными линиями.

В ответе укажите два числа - сначала минимальную сумму, затем количество команд телепорт.

Пример входных данных для поля 5×5:

A

B

C

D

E

A

B

C

D

E

1 -5 1 -4 -2 -2 1 -5 1 -4 -2 -2 2 -4 -4 5 2 -1 2 -4 -4 5 2 -1 3 -5 -1 -2 5 -2 3 -5 -1 -2 5 -2 4 3 -1 2 2 3 4 3 -1 2 2 3 5 -2 1 4 1 -5 5 -2 1 4 1 -5

Для таких данных ответом будут числа -24 и 2 (см. карту движения исполнителя на рисунке справа).