У прямокутної таблиці ~N~ x ~M~ (у кожній клітині якої записано деяке число) на початку гравець знаходиться в лівій верхній клітині. За один хід йому дозволяється переміщатися в сусідню клітку або вправо, або вниз (вліво і вверх переміщатися заборонено). При проході через клітку з гравця беруть стільки у.о., яке число записано в цій клітці (гроші беруть також за першу і останню клітини його шляху).

Потрібно знайти мінімальну суму у.о., заплативши яку гравець може потрапити в правий нижній кут.

Формат вхідних даних

У стандартному потоці міститься два числа ~N~ і ~M~ - розміри таблиці ~(1 ≤ N ≤ 20,1 ≤ M ≤ 20)~.

Потім йде ~N~ рядків по ~M~ чисел в кожній - розміри штрафів в у.о. за проходження через відповідні клітини (числа від 0 до 100).

Формат вихідних даних

У стандартний потік вивести мінімальну суму, витративши яку можна потрапити в правий нижній кут.

Приклад вхідних даних

3 4
1 1 1 1
5 2 2 100
9 4 2 1

Приклад вихідних даних

8