2. Самый дешевый путь

Не решаласьСредняя

В каждой клетке прямоугольной таблицы $N \times M$ записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).

Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.

Формат ввода

Вводятся два числа N и M — размеры таблицы ($1 \le N \le 20$, $1 \le M \le 20$). Затем идет N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).

Формат вывода

Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.

Ограничения

Ограничение времени

1 с

Ограничение памяти

256 МБ

Пример 1

Ввод
5 5
1 1 1 1 1
3 100 100 100 100
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1
Вывод
11

Теги

Нужно войти, чтобы отправить решение.Войти