Farmer John comprou terras nas Caraíbas e tentará criar vacas leiteiras numa grande quinta composta por ilhas. Fiel aos costumes, quer cercar todas as ilhas.

Cada ilha é um polígono. Cerca um lado de cada vez, entre vértices consecutivos, no sentido horário. Para cercar todas, deve a certa altura viajar de barco às outras.

Pode começar em qualquer vértice e, em qualquer um encontrado, ir a um vértice de outra ilha, cercá-la por completo e voltar IMEDIATAMENTE ao mesmo vértice original pelo mesmo caminho. Cada viagem tem custo definido por uma matriz.

As ilhas são descritas por $N$ $(3 \le N \le 500)$ pares $V1$,$V2$ $(1 \le V1 \le N; 1 \le V2 \le N)$; deve descobrir como se juntam em ilhas. Os vértices têm números $1,\ldots,N$.

Os custos de barco entre cada par estão numa matriz simétrica com elementos $0,\ldots,1000$.

Qual é o custo mínimo de cercar todas as ilhas?

Entrada

• Linha $1$: inteiro $N$.

• Linhas $2,\ldots,N+1$: cada uma descreve uma borda com inteiros $V1$, $V2$ separados por espaço.

• Linhas $N+2,\ldots,2\times N+1$: linha $i-N-1$ contém $N$ inteiros da linha $i$ da matriz: $Row_{i}$.

Saída

• Linha $1$: inteiro, custo mínimo de construir a cerca.

Exemplos

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

Saída 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

As três ilhas são $\{1,7,3,6,10\}$, $\{4,5,11\}$ e $\{2,9,8,12\}$. A matriz dá os custos; de $1$ a $2$ custa $15$.

Há várias soluções. FJ parte de $3$, passa por $7$ e para em $1$, vai a $11$, depois $4,5,11$. Volta a $1$, vai a $12$, depois $2,9,8,12$. Finalmente volta a $1$ e segue $10,6,3,7$. A ida e volta de $1$ a $11$ custa $8 \times 2 = 16$, de $1$ a $12$ $7 \times 2 = 14$, total $30$.

Autor do problema: Fatih Gelgi, 2008