На складе устроены проходы в виде прямоугольной сетки размером n x m. В каждой клетке указан неотрицательный целый тариф — цена за въезд робота в эту клетку.

Робот начинает движение из клетки (1, 1) и должен добраться до клетки (n, m). За один ход он может переместиться в соседнюю по стороне клетку: вверх, вниз, влево или вправо, если такая клетка существует.

При каждом перемещении робот платит тариф клетки, в которую въезжает. Тариф стартовой клетки (1, 1) не учитывается, так как робот уже находится в ней в начале.

Требуется определить минимальную суммарную стоимость, необходимую роботу, чтобы добраться из (1, 1) в (n, m).

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

В первой строке заданы два целых числа n и m.

Далее следуют n строк, в каждой из которых записано по m целых чисел — тарифы клеток склада.

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

Выведите одно целое число — минимальную суммарную стоимость пути робота из клетки (1, 1) в клетку (n, m).

Ограничения

• 1 <= n, m <= 1000
• n * m <= 200000
• 0 <= стоимость клетки <= 1000

Примеры

Пример 1

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

1 1
0

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

0

Пример 2

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

2 2
7 1
1000 0

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

1