Farmer John ha comprato terreni nei Caraibi e proverà ad allevare mucche da latte in una grande fattoria di isole. Fedele alle abitudini, vuole recintarle tutte.

Ogni isola è un poligono. Recinta un lato tra vertici consecutivi alla volta, in senso orario. Per recintarle tutte deve prima o poi raggiungere le altre in barca.

Può partire da qualsiasi vertice e, in ogni vertice incontrato, andare a un vertice di un’altra isola, recintarla tutta e tornare IMMEDIATAMENTE allo stesso vertice originale lungo lo stesso percorso. Ogni viaggio ha un costo dato da una matrice.

Le isole sono descritte da $N$ $(3 \le N \le 500)$ coppie $V1$,$V2$ $(1 \le V1 \le N; 1 \le V2 \le N)$; devi capire come formano isole. I vertici sono numerati $1,\ldots,N$.

Una matrice simmetrica con elementi $0,\ldots,1000$ dà il costo in barca tra ogni coppia.

Qual è il costo minimo per recintare tutte le isole?

Input

• Riga $1$: intero $N$.

• Righe $2,\ldots,N+1$: ogni riga descrive un bordo con interi $V1$, $V2$ separati da spazio.

• Righe $N+2,\ldots,2\times N+1$: riga $i-N-1$ contiene $N$ interi della riga $i$ della matrice: $Row_{i}$.

Output

• Riga $1$: intero, costo minimo della recinzione.

Esempi

Input 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

Output 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

Tre isole: $\{1,7,3,6,10\}$, $\{4,5,11\}$ e $\{2,9,8,12\}$. I costi sono nella matrice; da $1$ a $2$ è $15$.

Esistono più soluzioni. FJ parte da $3$, poi $7$, si ferma a $1$, va a $11$, poi $4,5,11$. Torna a $1$, va a $12$, poi $2,9,8,12$. Infine torna a $1$ e continua $10,6,3,7$. Andata e ritorno da $1$ a $11$ costa $8 \times 2 = 16$, da $1$ a $12$ $7 \times 2 = 14$, totale $30$.

Autore del problema: Fatih Gelgi, 2008