問題文

$H$ 行 $W$ 列の格子状の道の区画で区切られた街があります。

セパくんは、上から $1$ 行目のいずれかの区画からスタートし、$H$ 行目の区画のいずれかに向かおうとしています。

セパくんは、自分がいる区画から上下左右に隣接する道の区画へ移動することができます。

やきとりくんは、セパくんが $H$ 行目の区画のいずれにも到達できないように壁を建てることにしました。

しかし、壁を建てるには以下のルールを守らなくてはいけません。

• $1$ 行目と $H$ 行目の区画に壁を置くことはできない。
• 上から $i$ 行目、左から $j$ 列目の区画 $(2 \leq i \leq H - 1, 1 \leq j \leq W)$ に壁を立てるには、$A_{i,j}$ のコストがかかる。ただし、$A_{i,j} = -1$ の場合は壁を置くことができない。

セパくんが $H$ 行目の区画のいずれにも到達できないように壁を置いたときにかかる最小のコストを求めてください。

また、どのように壁を配置してもセパくんが $H$ 行目の区画のいずれかに到達できる場合には $-1$ を出力してください。

制約

• $3 \leq H, W \leq 800$
• $1 \leq A_{i,j} \leq 800$ または $A_{i,j} = -1$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$  
$A_{2,1}$ $A_{2,2}$ ... $A_{2,W}$  
$A_{3,1}$ $A_{3,2}$ ... $A_{3,W}$  
$\vdots$

$A_{H-1,1}$ $A_{H-1,2}$ ... $A_{H-1,W}$  

出力

問題の答えを一行に出力せよ。

どのように壁を配置してもセパくんが $H$ 行目の区画のいずれかに到達できる場合には $-1$ を出力せよ。

サンプル

5 4
2 5 7 11
1 6 9 10
3 4 8 12

23

....
....
#..#
.##.
....

5 4
2 5 -1 11
-1 6 9 10
3 -1 8 12

26

....
#...
.#.#
..#.
....

5 4
2 5 -1 11
-1 -1 -1 10
3 -1 8 12

-1