Farmer John kaufte Land in der Karibik und möchte Milchkühe auf einer großen Farm aus Inseln halten. Gewohnheitsgemäß will er alle Inseln umzäunen.

Jede Insel ist ein Polygon. Er umzäunt eine Seite zwischen aufeinanderfolgenden Eckpunkten nach der anderen, im Uhrzeigersinn. Für alle Inseln muss er irgendwann mit dem Boot zu anderen fahren.

Er darf an jedem Eckpunkt beginnen und an jedem erreichten Eckpunkt zu einem Punkt einer anderen Insel fahren, diese ganz umzäunen und SOFORT auf demselben Weg zum selben Punkt der ursprünglichen Insel zurückkehren. Eine Matrix gibt die Kosten jeder Bootsfahrt.

Die Inseln sind durch $N$ $(3 \le N \le 500)$ Paare $V1$,$V2$ $(1 \le V1 \le N; 1 \le V2 \le N)$ beschrieben; du musst ihre Zusammenstellung zu Inseln ermitteln. Punkte sind $1,\ldots,N$ nummeriert.

Eine symmetrische Matrix mit Einträgen $0,\ldots,1000$ gibt Bootskosten zwischen allen Punkten an.

Was kostet das Umzäunen aller Inseln mindestens?

Eingabe

• Zeile $1$: ganze Zahl $N$.

• Zeilen $2,\ldots,N+1$: jeweils eine Inselgrenze durch ganze Zahlen $V1$, $V2$ mit Leerzeichen.

• Zeilen $N+2,\ldots,2\times N+1$: Zeile $i-N-1$ enthält $N$ ganze Zahlen für Matrixzeile $i$: $Row_{i}$.

Ausgabe

• Zeile $1$: ganze Zahl, minimale Zaunbaukosten.

Beispiele

Eingabe 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

Ausgabe 1

30

Hinweis

  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

Drei Inseln: $\{1,7,3,6,10\}$, $\{4,5,11\}$ und $\{2,9,8,12\}$. Die Matrix gibt Kosten; etwa kostet $1$ nach $2$ $15$.

Es gibt mehrere Lösungen. FJ beginnt bei $3$, dann $7$, stoppt bei $1$, fährt zu $11$, dann $4,5,11$. Zurück zu $1$, dann zu $12$ und $2,9,8,12$. Schließlich zurück zu $1$ und weiter $10,6,3,7$. Hin und zurück von $1$ nach $11$ kostet $8 \times 2 = 16$, von $1$ nach $12$ $7 \times 2 = 14$, zusammen $30$.

Aufgabenautor: Fatih Gelgi, 2008