У прямокутної таблиці \(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