题目描述

约翰在加勒比海买下地产，准备在这里的若干个岛屿上养奶牛．所以，他要给所有岛屿围上篱笆．每个岛屿都是多边形．他沿着岛屿的一条边界朝一个方向走，有时候坐船到另一 个岛去．

他可以从任意一个多边形顶点开始修篱笆的工作；在任意一个到达的顶点，他可以坐船去另一个岛屿的某个顶点，但修完那个岛的篱笆，他必须马上原路返回这个出发的岛屿顶点 ．

任意两个顶点间都有肮线，每条航线都需要一定的费用．请帮约翰计算最少的费用，让他修完所有篱笆．

输入格式

第$\red{1}$行输入$\red{N(3≤}$$\red{N≤}$$\red{500)，}$表示所有岛屿多边形的个数．

接下来$\red{N}$行每行输入两个整数$\red{V1}$和$\red{V2(1≤}$$\red{V1≤}$$\red{N}$;$\red{1≤}$$\red{V2≤}$$\red{N)，}$表示一条构成岛屿的线段的两个端点．

接下来输入$\red{N}$行$\red{N}$列的矩阵，表示两个顶点间航行所需费用．

输出格式

一个整数，最少费用．

样例

输入样例

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

提示

输入中的三个岛屿是这样的：

约翰可行的一种走法是:从$\red{3}$出发，到$\red{7，}$再到$\red{1，}$然后由$\red{1}$坐船到$\red{11，}$走$\red{4，}$$\red{5，}$$\red{11}$再回到$\red{1.}$

然后再由$\red{1}$坐船到$\red{12，}$走$\red{2，}$$\red{9，}$$\red{8，}$$\red{12}$回到$\red{1.}$最后走$\red{10，}$$\red{6，}$$\red{3，}$$\red{7}$回到原点，两次坐船分别费用是$\red{8}$和$\red{7，}$来回总费用是$\red{30}$