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$ 行含 $N$ 整數，描述費用矩陣第 $i$ 行 $Row_{i}$。

輸出格式

• 第 $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