問題文

$N$ 階建てのマンションがあり、各階には $M$ 部屋あります。

このマンションにはエレベーターがなかったので、新たにエレベーターを設置することにしました。そのため、いくつかの部屋をエレベーター設置のために取り壊すことにしました。

$i$ 階にある $j$ 番目の部屋を取り壊すには費用 $A_{i,j}$ がかかります。

部屋を取り壊した後、エレベーターを次のように設置します。

• $i_1,i_2,j \ (1\le i_1\lt i_2\le N, 1\le j\le M)$ に対して、$i_1,i_1+1,\ldots,i_2$ 階の $j$ 番目の部屋がすべて取り壊されているとき、この場所にエレベーターを設置することができる。これにより $i_1,i_1+1,\ldots,i_2$ 階が互いに行き来可能になる。
• エレベーターは複数台設置してもよい。

エレベーターを使って $1$ 階からすべての階に行けるようにしたいです。エレベーターは複数台使ってもよいです。

$1$ 階からすべての階に行けるようにするために必要な、部屋を取り壊す費用の合計の最小値を求めてください。

制約

• $1\le N,M\le 1000$
• $1\le A_i\le 10^9$
• 入力はすべて整数

入力

$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}$

出力

$1$ 階からすべての階に行けるようにするために必要な部屋を取り壊す費用の最小値を出力してください。

サンプル

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