## 24 hour archive: Problem

###
** 2191
- Rub Task** ** 2191 - Rub Task** ** 2191 - Rub Task**

#### Description

Rub is a boy lover of mathematics, and specifically likes many grids. Searching the internet he came across an old problem, which gave him a NxM grid, he wants to determine a sequence of squares in the grid from the leftmost column to the rightmost column, and the sum of all sequence elements is minimized. Only allowed in the sequence boxes that share at least one side adjacent to the four directions.

;jsessionid=0B08964DD49D6D93B63A9F1C50233A13Rub is a boy lover of mathematics, and specifically likes many grids. Searching the internet he came across an old problem, which gave him a NxM grid, he wants to determine a sequence of squares in the grid from the leftmost column to the rightmost column, and the sum of all sequence elements is minimized. Only allowed in the sequence boxes that share at least one side adjacent to the four directions.

;jsessionid=0B08964DD49D6D93B63A9F1C50233A13Rub is a boy lover of mathematics, and specifically likes many grids. Searching the internet he came across an old problem, which gave him a NxM grid, he wants to determine a sequence of squares in the grid from the leftmost column to the rightmost column, and the sum of all sequence elements is minimized. Only allowed in the sequence boxes that share at least one side adjacent to the four directions.

;jsessionid=0B08964DD49D6D93B63A9F1C50233A13#### Input specification

The first line of the input is two integers N and M, 1 <= N, M <= 100, the following N lines have M integers 0 <= Mi, j <= 100000.

;jsessionid=0B08964DD49D6D93B63A9F1C50233A13The first line of the input is two integers N and M, 1 <= N, M <= 100, the following N lines have M integers 0 <= Mi, j <= 100000.

;jsessionid=0B08964DD49D6D93B63A9F1C50233A13The first line of the input is two integers N and M, 1 <= N, M <= 100, the following N lines have M integers 0 <= Mi, j <= 100000.

;jsessionid=0B08964DD49D6D93B63A9F1C50233A13#### Output specification

The output is an integer that represents the minimum sum of the sequence that rub must find.

;jsessionid=0B08964DD49D6D93B63A9F1C50233A13The output is an integer that represents the minimum sum of the sequence that rub must find.

;jsessionid=0B08964DD49D6D93B63A9F1C50233A13#### Sample input

`3 3`

1 0 5

5 1 7

3 1 1

#### Sample output

`4`