Description

Farmer John 在加勒比海购置了一片地产，准备在由一系列岛屿组成的农场上养奶牛。 出于他的意愿，他要把所有的岛屿都用篱笆围上。 每个岛都是多边形的。每一次，FJ 会给多边形的一个边（即相邻的两个顶点之间）装上篱笆。对于整个岛屿，他会按照顺时针顺序装上篱笆。由于他想要给所有的岛屿都装上篱笆，某些时候，他必须从一个岛屿坐船到另一个岛屿去。
FJ 可以从任何一个顶点开始装篱笆，也可以从任何一个顶点坐船到另一个岛的某个顶点上，从这个顶点开始把该岛屿的篱笆全都装好，然后马上坐船原路返回。保证任意两个顶点间都有航线。在任意两个顶点之间坐船的费用会在一个矩阵中给出。

所有的岛屿由给定的 $N$ 对顶点 $V_1$，$V_2$ 描述（即：给定顶点 $V_1$ 与 $V_2$ 相邻）。每个顶点具体属于哪个岛屿不会在输入中给出。所有顶点由 $1$ 到 $N$ 标号。
在顶点间坐船旅行的费用由一个 $N \times N$ 的矩阵给出。保证两个岛屿间两个方向的旅行费用相等且不会超过 $1000$。

请求出 FJ 把篱笆装完所需要的最小花费。

Input Format

第 $1$ 行一个整数 $N$。

第 $2$ 至第 $N+1$ 行：每行包含两个整数 $V_1$ 和 $V_2$，表示这两个顶点在同一个岛屿上且相邻。

第 $N+2$ 行至第 $2\times N+1$ 行：每行包含 $N$ 个整数，第 $i+N+1$ 行的第 $j$ 个整数表示从 $i$ 号顶点坐船到第 $j$ 号顶点的花费。

Output Format

一行一个整数，表示 FJ 把篱笆装完所需要的最小花费。

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 

30 

Hint

对于所有数据，保证：

• $3 \leq N \leq 500$
• $1 \leq V_1,V_2 \leq N$
• 任意两个顶点之间的旅行花费 $\leq 1000$