H. Blocking the Way
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Alice is playing a puzzle game where she slides a tile piece to move it to its destination on a rectangular grid board consisting of unit squares. Only parallel moves of the piece on the game board are allowed; no rotations nor lifting up. Some squares on the board are marked no-entry where any parts of the tile piece should not enter.

The tile piece is composed of a number of unit squares joined tightly along their edges. The tile piece is initially placed to touch both the left and the top ends of the board. The goal of Alice is to slide the tile piece to make it touch both the right and the bottom ends of the board.

Bob, on the other hand, wants to make Alice's goal unachievable by changing some squares to no-entry. Each square, except for those initially covered by the tile piece, can be made no-entry by paying the specified number of coins. Compute the minimum number of coins Bob has to pay in total to make Alice's goal unachievable.

Input

The input consists of multiple datasets, each in the following format.

$$$r$$$ $$$c$$$
$$$a_{1,1}$$$ $$$\ldots$$$ $$$a_{1,c}$$$
$$$\vdots$$$
$$$a_{r,1}$$$ $$$\ldots$$$ $$$a_{r,c}$$$

Here, $$$r$$$ and $$$c$$$ are integers between $$$2$$$ and $$$100$$$, inclusive, representing the numbers of rows and columns of the board, respectively. The following $$$a_{i,j}$$$ $$$(1 \le i \le r, 1 \le j \le c)$$$ are integers between $$$-1$$$ and $$$10^9$$$, inclusive. Here, $$$a_{i,j}$$$ represents the state of the square $$$(i, j)$$$ on row $$$i$$$ and column $$$j,$$$ as follows.

  • If $$$a_{i,j} = -1$$$, the square is initially covered by the tile piece.
  • If $$$a_{i,j} = 0$$$, the square is no-entry from the beginning.
  • If $$$a_{i,j} \gt 0$$$, Bob can make the square <em>no-entry</em> by paying $$$a_{i,j}$$$ coins.

The number of $$$(i, j)$$$ satisfying $$$a_{i,j} = -1$$$ is between $$$1$$$ and $$$100,$$$ inclusive. All the squares corresponding to them are connected directly or indirectly with one or more of their edges. Furthermore, they are contiguous in each row and each column. That is, if $$$a_{i,j_1} = -1$$$ and $$$a_{i,j_2} = -1$$$ for two columns $$$j_1$$$ and $$$j_2$$$ in the same row $$$i$$$ where $$$j_1 \lt j_2$$$, then $$$a_{i,j} = -1$$$ for all $$$j$$$ such that $$$j_1 \lt j \lt j_2$$$. Similarly, if $$$a_{i_1,j} = -1$$$ and $$$a_{i_2,j} = -1$$$ for two rows $$$i_1$$$ and $$$i_2$$$ in the same column $$$j$$$ where $$$i_1 \lt i_2$$$, then $$$a_{i,j} = -1$$$ for all $$$i$$$ such that $$$i_1 \lt i \lt i_2$$$.

It is guaranteed that, in the initial state, the tile piece is placed so that some of its edges touch the left end of the board and some touch the top end. It is also guaranteed that Alice has not yet achieved her goal. That is, the following two conditions are satisfied.

  • There exists at least one $$$i$$$ satisfying $$$a_{i,1} = -1$$$ and at least one $$$j$$$ satisfying $$$a_{1,j} = -1$$$.
  • $$$a_{i,c} \not= -1$$$ for all $$$i$$$ or $$$a_{r,j} \not= -1$$$ for all $$$j.$$$

The end of the input is indicated by a line consisting of two zeros. The number of datasets does not exceed $$$50$$$. The sum of $$$r$$$ of all the datasets does not exceed $$$1000$$$. The sum of $$$c$$$ of all the datasets does not exceed $$$1000$$$. The total number of $$$(i, j)$$$ satisfying $$$a_{i,j} = -1$$$ of all the datasets does not exceed $$$1000$$$.

Output

For each dataset, output on a single line the minimum number of coins Bob has to pay.

Example
Input
3 3
-1 33 22
99 0 99
11 44 99
4 3
-1 90 10
-1 90 20
20 50 99
10 20 99
3 3
-1 33 22
99 99 99
11 44 0
3 4
99 -1 10 99
-1 -1 -1 99
99 -1 99 99
0 0
Output
33
40
0
10