Путь в матрице

Задана матрица размером n × m, содержащая неотрицательные целые числа, не превышающие 10000.

Соседние клетки матрицы – это клетки, номера столбцов или строк которых отличаются на 1. Путь от одной клетки матрицы до другой проходит только через соседние клетки.

Найти путь минимальной стоимости между левым верхним и правым нижним углами матрицы. Стоимость пути формируется как сумма элементов матрицы, через которые проходит путь. Разрешается двигаться в соседние клетки влево, вправо, вверх и вниз.

Входные данные

В первой строке содержатся числа n и m (1 ≤ n, m ≤ 10). Далее идет n строк, в каждой строке по m чисел, разделенных пробелом.

Выходные данные

Выведите стоимость минимального пути.

Примеры