Surround the Islands with Fence

Farmer John has bought a large farm made up of several islands and wants to raise dairy cows there. He wants to surround every island with fence.

Each island is shaped like a polygon. John fences one island at a time, moving clockwise around it and building fence one side at a time between consecutive vertices. Walking around the border of an island costs nothing.

To fence every island he must travel by boat to the others. John may start fencing at any vertex, and from any vertex he passes he may take a boat to some vertex on another island, fence all the way around that island, and then IMMEDIATELY return to the very same vertex of the original island along the same path he came. Thus each boat trip is a round trip and costs twice the one-way fare.

The cost of boating between each pair of vertices is given by a symmetric cost matrix.

The islands are given as $N$ vertex pairs $(V_1, V_2)$; you must work out how to assemble these edges into islands. Vertices are numbered $1$ through $N$, and each vertex belongs to exactly one island.

Find the minimum cost of surrounding all the islands with fence.

Constraints: $3 \le N \le 500$, $1 \le V_1, V_2 \le N$, and every boat cost is between $0$ and $1000$ inclusive.

• Line 1: an integer $N$.
• Lines 2 through $N+1$: each line gives two space-separated vertices $V_1$ and $V_2$ forming one side of an island's border.
• Lines $N+2$ through $2N+1$: the rows of the cost matrix. Line $i$ contains $N$ integers giving the boat cost from vertex $i$ to every other vertex. The matrix is symmetric.

• Print a single integer: the minimum cost of building the fence around all islands.

The figure below shows three islands.

  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

The three islands consist of vertices ${1,7,3,6,10}$, ${4,5,11}$, and ${2,9,8,12}$.

For instance, boating from vertex $1$ to vertex $11$, fencing the second island, and returning to $1$ costs $8 \times 2 = 16$; boating from $1$ to $12$, fencing the third island, and returning costs $7 \times 2 = 14$. The first island needs no boat trip because it is the starting island, so the total is $16 + 14 = 30$. More than one optimal route exists.