После неудачно написанного раунда Матвей понял, что ему не нравится программирование

Напишите на Python
После неудачно написанного раунда Матвей понял, что ему не нравится программирование, тогда он решил уйти изучать робототехнику.

Но когда он пришёл на занятие, ему дали следующее задание: есть поле, которое состоит из n
строк, пронумерованных от 1
до n
сверху вниз и m
столбцов, пронумерованных от 1
до m
слева направо. Обозначим значение в клетке в i
-й строке и j
-м столбце как ai,j
.

Изначально робот Матвея стоит в левом верхнем углу клетки a1,1
. Роботу нужно попасть в клетку an,m
в правый нижний угол. Робот Матвея может передвигаться только вправо и вниз, при этом за одно передвижение он проходит ровно на одну клетку. Обратите внимание, что правый верхний угол клетки ai,j
совпадает с левым верхним углом клетки ai,j+1
.

За переход робота из левого верхнего в правый верхний угол клетки (i,j)
Матвей должен заплатить ai,j⋅ai−1,j
бурлей, то есть за переход он тратит произведение значений в клетках, которые примыкают к проходимому ребру. Кроме того, если робот Матвея проходит по границе поля, то он тратит только такое количество бурлей, которое написано в клетке, примыкающей к проходимому ребру.

Вам необходимо сказать, какое минимальное количество бурлей Матвей может заплатить, чтобы его робот прошёл от левого верхнего угла клетки (1,1)
к правому нижнему углу клетки (n,m)
.

Входные данные
В первой строке даны два числа n,m
— количество строк и количество столбцов (1≤n,m≤500
).

В последующих n
строках даны по m
чисел — значения на поле (0≤ai,j≤106
).

Выходные данные
Выведите единственное число — минимальное количество денег, которое надо заплатить Матвею.

Пример
входные данные
3 3
1 3 2
4 2 7
6 4 2
выходные данные
17

0