A - Moving Piece Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

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) に到達できないようにしたいです。このとき、配置した壁のコストの和として考えられる最小値を求めてください。

制約

  • 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
  • 入力は全て整数

入力

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

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}

出力

答えを出力せよ。

入力例 1

1
1 -1 5
2 4 6
3 -1 7

出力例 1

10

入力例 2

2
8 1 -1 5 5
7 4 9 9 3
3 2 1 1 8
4 4 3 3 4
3 5 -1 5 8

出力例 2

10