информатика

Дано клетчатое поле размера N

×

M

��

. У клетки из строки i

�

 и столбца j

�

 координаты (

i

,

j

)

(�,�)

. У этого поля есть две особенности:

1. В каждой клетке поля записано целое положительное число
2. Некоторые клетки поля являются телепортами

Роботу нужно пройти из левой верхней клетки с координатами (

1

,

1

)

(1,1)

 до правой нижней c координатами (

N

,

M

)

(�,�)

.При этом робот из текущей клетки может переходить на одну клетку вправо или на одну клетку вниз.

Также у робота есть одна возможность телепорта. Это значит, что если он попал в клетку-телепорт, то он может телепортироваться в любую другую клетку-телепорт. При этом, когда произойдёт одна телепортация, то все телепорты выключатся и больше не будут работать.

Стоимостью пути назовём среднее арифметическое чисел во всех клетках (не обязательно целое), которые посетил робот (включая левую верхнюю и правую нижнюю).

При этом, если робот посетил одну клетку несколько раз, то она учтётся в ответе несколько раз. Обратите внимание, что робот может телепортироваться в ту же клетку, в которой он находится. (Тогда эта клетка учтётся два раза в ответе)

Найдите максимальную стоимость пути, по которому может пройти робот.