AT_pakencamp_2022_day3_a Moving Piece

$ 2N+1 $ 行、 $ 2N+1 $ 列のマス目があります。上から $ i $ 行目、左から $ j $ 列目のマス目のことをマス $ (i,j) $ と呼ぶことにします。 また、 $ (2N+1) \times (2N+1) $ 整数行列 $ A $ が与えられます。 ここで、マス $ (1,N+1),(2N+1,N+1) $ を除く各マスには壁を設置することができ、マス $ (i,j) $ に壁を設置する**コスト**は $ A_{i,j} $ です。 いま、マス $ (1,N+1) $ に駒が置かれています。この駒は今いるマス目と上下左右に隣接し、かつ壁が置かれていないマス目に移動するという操作を任意の回数行うことができます。 厳密には、マス $ (x,y) $ に駒が置かれている時、マス $ (x',y') $ であって次の条件を全て満たすマスに移動することができます。 - $ 1 \le x',y' \le 2N+1 $ - マス $ (x',y') $ に壁が設置されていない。 - $ |x-x'|+|y-y'| = 1 $ あなたは、壁をいくつか配置することで駒がどんな動きをしたとしてもマス $ (2N+1,N+1) $ に到達できないようにしたいです。このとき、配置した壁のコストの和として考えられる最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_{1,1} $ $ A_{1,2} $ $ \cdots $ $ A_{1,2N+1} $ $ A_{2,1} $ $ A_{2,2} $ $ \cdots $ $ A_{2,2N+1} $ $ \vdots $ $ A_{2N+1,1} $ $ A_{2N+1,2} $ $ \cdots $ $ A_{2N+1,2N+1} $

答えを出力せよ。

### Constraints - $ 1 \le N \le 300 $ - $ (1,N+1),(2N+1,N+1) $ でない $ (i,j) $ について、 $ 1 \le A_{i,j} \le 10^9 $ - $ A_{1,N+1} = A_{2N+1,N+1} = -1 $ - 入力は全て整数