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