Fencing the Islands

Farmer John has bought property in the Caribbean and plans to raise dairy cows on a farm composed of several islands. Each island is in the shape of a polygon and is described by a set of edges given as consecutive pairs of vertices (when traversed in clockwise order). John starts fencing at any vertex on an island and may, at any vertex, take a boat trip to another island. When he does, he immediately fences the entire target island (again, in clockwise order) and then returns by the same boat route. The cost of each boat trip is defined by a symmetric cost matrix and each trip’s cost is incurred twice (going and coming back).

Your task is to determine the minimum total boat cost required in order to fence all the islands. Note that the fencing of an island incurs no cost; only the boat trips do.

Hint: The optimal strategy is equivalent to selecting one island as the starting island (with no boat cost) and connecting the remaining islands using boat trips. For any pair of islands, the boat travel cost is 2 multiplied by the minimum cost between any vertex on one island and any vertex on the other island. Thus, the answer is the total weight of the minimum spanning tree (MST) on this “island graph”.

inputFormat

The input begins with an integer E (3 ≤ E ≤ 500), the total number of fence sides. Each of the following E lines contains two integers V₁ and V₂, indicating an edge between vertices V₁ and V₂. These edges form disjoint cycles, with each cycle representing an island. The vertices are numbered from 1 to N, where N is the maximum vertex number encountered in these E lines.

After the edges, there is an integer N on a separate line, representing the total number of vertices. Following that are N lines, each containing N space‐separated integers. The j^th number in the i^th row is the boat travel cost from vertex i to vertex j. The cost matrix is symmetric, and each cost is an integer in the range 0 to 1000.

outputFormat

Output a single integer: the minimum total boat cost required to fence all the islands.

sample

6
1 2
2 3
3 1
4 5
5 6
6 4
6
0 5 5 10 10 10
5 0 5 10 10 10
5 5 0 10 10 10
10 10 10 0 2 2
10 10 10 2 0 2
10 10 10 2 2 0

20