Farmer John はカリブ海の土地を買い、島々からなる大農場で乳牛を育てようとしています。いつもの習慣で全島を柵で囲みます。

各島は多角形です。隣接頂点間の一辺ずつ、島を時計回りに囲みます。全島を囲むため、途中で船で他の島へ行く必要があります。

任意の頂点から開始し、到達した任意の頂点で別の島の頂点へ移動できます。その島を一周囲み、すぐに同じ経路で元の島の同じ頂点へ戻ります。各船旅の費用は行列で与えられます。

島は $N$ $(3 \le N \le 500)$ 組の頂点 $V1$、$V2$ $(1 \le V1 \le N; 1 \le V2 \le N)$ で表され、組み合わせて島を特定してください。頂点は $1,\ldots,N$ と番号付けされています。

頂点対間の船の費用は対称行列で、要素の範囲は $0,\ldots,1000$ です。

全島を柵で囲む最小費用はいくらですか。

入力

• $1$ 行目：整数 $N$。

• $2,\ldots,N+1$ 行目：各行は空白区切りの整数 $V1$ と $V2$ で島の境界を表します。

• $N+2,\ldots,2\times N+1$ 行目：$i-N-1$ 行目は費用行列の第 $i$ 行 $Row_{i}$ を表す $N$ 整数。

出力

• $1$ 行目：柵建設の最小費用の整数。

入出力例

入力 1

12
1 7
7 3
3 6
6 10
10 1
2 12
2 9
8 9
8 12
11 5
5 4
11 4
0 15 9 20 25 8 10 13 17 8 8 7
15 0 12 12 10 10 8 15 15 8 8 9
9 12 0 25 20 18 16 14 13 7 12 12
20 12 25 0 8 13 14 15 15 10 10 10
25 10 20 8 0 16 20 18 17 18 9 11
8 10 18 13 16 0 10 9 11 10 8 12
10 8 16 14 20 10 0 18 20 6 16 15
13 15 14 15 18 9 18 0 5 12 12 13
17 15 13 15 17 11 20 5 0 22 8 10
8 8 7 10 18 10 6 12 22 0 11 12
8 8 12 10 9 8 16 12 8 11 0 9
7 9 12 10 11 12 15 13 10 12 9 0

出力 1

30

注記

  1        10            4
    xxxxxxx              x
   xxxxxxxxx            xxxx
7 xxxxxxxxxxx 6        xxxxxxx
 xxxxxxxxxxx       11 xxxxxxxxxx 5
  xxxxxxx
   xxx
  3         12 xxxxxxx 2
              xxxxxxxx
              xxxxxxxx
             xxxxxxxxx
             xxxxxxxxx
            xxxxxxxxxx
            xxxxxxxxxx
          8 xxxxxxxxxx 9

例の三島は $\{1,7,3,6,10\}$、$\{4,5,11\}$、$\{2,9,8,12\}$ です。費用は行列で、例えば $1$ から $2$ は $15$。

解は複数あります。一つは FJ が $3$、$7$ を経て $1$ で止まり、$11$ に渡って $4,5,11$ と進む方法です。$1$ に戻り $12$ に渡って $2,9,8,12$。最後に $1$ に戻り $10,6,3,7$ と続けます。$1$ と $11$ の往復は $8 \times 2 = 16$、$1$ と $12$ は $7 \times 2 = 14$、計 $30$。

問題作成者：Fatih Gelgi、2008