Grid Game with Restricted Moves

You are given an ( n\times m ) grid with an integer written in every cell. For convenience, let the top–left cell be ( (1,1) ) and the bottom–right cell be ( (n,m) ).\n\nThe game is played as follows: Small A may start by entering any cell in the bottom row (row ( n )). Suppose that he enters row ( i ) for the first time at column ( r_i ) (i.e. at cell ( (i, r_i) )). Then, while he is in row ( i ), the following rules apply:\ (\bullet) If he is at the first–entered cell ( (i, r_i) ), he is allowed to jump either left or up.\ (\bullet) If he is at any other cell in row ( i ), he is allowed to jump left, right, or up.\ (bullet) He cannot jump out of the grid except when in the first row; a jump upward from row 1 ends the game.\n\nThe score of a game is defined as the sum of all the numbers on the cells that Small A passes through (note that if a cell is visited more than once its value is added each time). Small A would like to know the minimum possible score achievable by following some valid sequence of moves.\n\nA crucial observation is that when Small A enters a new row at column ( r ), he may choose to traverse a contiguous segment of that row ( [L, R] ) (with ( L \le r \le R )) before jumping upward. The cost incurred in that row is the sum of the numbers in the cells ( (i, L), (i, L+1), \dots, (i, R) ) and he may jump upward from any cell within the segment. For row 1 the game ends after the horizontal movement. For rows 2 to ( n ), if Small A exits row ( i ) from column ( p ) then he will enter row ( i-1 ) at column ( p ).\n\nYour task is to compute the minimum total score achievable.\n\n(\textbf{Input Constraints:}) It is guaranteed that ( n ) and ( m ) are small enough so that an ( O(n\cdot m^3) ) solution will run in the allotted time.

inputFormat

The first line contains two integers ( n ) and ( m ). The next ( n ) lines each contain ( m ) integers, where the ( i )th line describes row ( i ) of the grid (with row 1 being the top row and row ( n ) being the bottom row).

outputFormat

Output a single integer: the minimum score Small A can achieve.

sample

2 2
1 2
3 4

4