Олимпиадный тренинг

Задача . Минимальный путь в таблице


В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке.
За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено).
При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).
 
Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.
 
Входные данные
В первой строке записаны два числа N и M - размеры таблицы (\(1<=N<=20\), \(1<=M<=20\)). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).
 
Выходные данные
Выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.
 
 
Примеры
Входные данные Выходные данные
1
3 4
1 1 1 1
5 2 2 100
9 4 2 1
8



time 1000 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6471
C#1
Java1
Python269
Комментарий учителя