Farmer John compró tierras en el Caribe e intentará criar vacas lecheras en una gran granja de islas. Fiel a sus costumbres, quiere cercarlas todas.

Cada isla es un polígono. Cerca un lado cada vez, entre vértices consecutivos, avanzando en sentido horario. Para cercar todas, en algún momento debe viajar en barco a las otras.

Puede empezar en cualquier vértice y, en cualquiera que encuentre, ir a un vértice de otra isla, cercarla por completo y volver INMEDIATAMENTE al mismo vértice original por el mismo camino. Cada viaje tiene un coste dado por una matriz.

Las islas se describen por $N$ $(3 \le N \le 500)$ pares $V1$,$V2$ $(1 \le V1 \le N; 1 \le V2 \le N)$; debes descubrir cómo forman islas. Los vértices se numeran $1,\ldots,N$.

Los costes en barco entre cada par se dan en una matriz simétrica con elementos $0,\ldots,1000$.

¿Cuál es el coste mínimo de cercar todas las islas?

Entrada

• Línea $1$: entero $N$.

• Líneas $2,\ldots,N+1$: cada una describe un borde con enteros $V1$, $V2$ separados por espacio.

• Líneas $N+2,\ldots,2\times N+1$: línea $i-N-1$ contiene $N$ enteros de la fila $i$ de la matriz: $Row_{i}$.

Salida

• Línea $1$: entero, coste mínimo de construir la cerca.

Ejemplos

Entrada 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

Salida 1

30

Nota

  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

Las tres islas son $\{1,7,3,6,10\}$, $\{4,5,11\}$ y $\{2,9,8,12\}$. La matriz da los costes; de $1$ a $2$ cuesta $15$.

Hay varias soluciones. FJ parte de $3$, pasa por $7$ y para en $1$, va a $11$, luego $4,5,11$. Vuelve a $1$, va a $12$, luego $2,9,8,12$. Finalmente vuelve a $1$ y sigue $10,6,3,7$. La ida y vuelta de $1$ a $11$ cuesta $8 \times 2 = 16$, la de $1$ a $12$ $7 \times 2 = 14$, total $30$.

Autor del problema: Fatih Gelgi, 2008