Rub es un niño amante de las matemáticas, y específicamente le gustan muchas las cuadrículas. Al buscar en internet se encontró con un viejo problema, dada una cuadrícula \(N × M\), se quiere determinar una secuencia de cuadrados en la cuadrícula desde la columna de la izquierda hasta la columna de la derecha, tal que la suma de todos los elementos de la secuencia sea mínima. Solo se permite como cuadros adyacentes de la secuencia aquellos que comparten al menos un lado en las cuatro direcciones.

Entrada

La primera línea de la entrada son dos enteros ~N~ y ~M~, ~1 \leq N, M \leq 100~, las siguientes ~N~ líneas tienen ~M~ enteros ~0 \leq M (i, j) \leq 100 000~.

Salida

La salida es un número entero que representa la suma mínima de la secuencia que debe encontrar Rub.

Ejemplo de Entrada

3 3
1 0 5
5 1 7
3 1 1

Ejemplo de Salida

4