Problem Statement

There is an apartment building with $N$ floors, and each floor has $M$ rooms.

Since this building had no elevator, it has been decided to install new elevators. For this purpose, some rooms will be demolished to make space for the elevators.

Demolishing the $j$-th room on floor $i$ costs $A_{i,j}$.

After demolishing rooms, elevators are installed as follows.

• For $i_1,i_2,j \ (1\le i_1\lt i_2\le N, 1\le j\le M)$, if the $j$-th rooms on floors $i_1,i_1+1,\ldots,i_2$ have all been demolished, an elevator can be installed at this location. This makes it possible to travel among floors $i_1,i_1+1,\ldots,i_2$.
• Multiple elevators may be installed.

We want to make it possible to reach every floor from floor $1$ using elevators. Multiple elevators may be used.

Find the minimum total cost of demolishing rooms required to make every floor reachable from floor $1$.

Constraints

• $1\le N,M\le 1000$
• $1\le A_i\le 10^9$
• All inputs are integers

Input

$N$ $M$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,M}$
$A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,M}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,M}$

Output

Output the minimum cost of demolishing rooms required to make every floor reachable from floor $1$.

Sample

3 4
9 9 9 1
1 9 9 1
1 9 9 9

4

4 3
2 3 6
2 3 6
6 3 2
6 3 2

12

1 1
998244353

0