Задача "Путь в таблице"

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

Стоимостью пути называется сумма чисел, записанных в клетках, по которым проходит путь. Найдите минимальную стоимость пути для путешественника.

Формат входных данных. Вводятся числа N и M - размеры таблицы (1≤N≤30, 1≤M≤30). Далее записано N строк по M чисел в каждой - числа, записанные в клетках таблицы (натуральные числа, не превышающие 100).

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

Пример

6 5
 1 10  1  1  2
 1  1  1 10  1
10 10 10 10  1
 1  1  1  1  1
 1  1  1  1 10
 1  1  1  1  1

15