Farmer John kupił ziemię na Karaibach i chce hodować krowy mleczne na dużej farmie z wysp. Jak zwykle pragnie otoczyć wszystkie płotem.

Każda wyspa jest wielokątem. Grodzi po jednym boku między kolejnymi wierzchołkami, zgodnie z zegarem. Aby ogrodzić wszystkie, musi czasem płynąć łodzią na inne.

Może zacząć w dowolnym wierzchołku i w każdym napotkanym płynąć do wierzchołka innej wyspy, ogrodzić ją całą i NATYCHMIAST wrócić tą samą drogą do tego samego wierzchołka pierwszej wyspy. Koszty każdej podróży określa macierz.

Wyspy opisuje $N$ $(3 \le N \le 500)$ par $V1$,$V2$ $(1 \le V1 \le N; 1 \le V2 \le N)$; musisz ustalić, jak tworzą wyspy. Wierzchołki mają numery $1,\ldots,N$.

Symetryczna macierz o elementach $0,\ldots,1000$ daje koszt łodzi między każdą parą.

Jaki jest minimalny koszt ogrodzenia wszystkich wysp?

Wejście

• Wiersz $1$: całkowite $N$.

• Wiersze $2,\ldots,N+1$: każdy opisuje granicę wyspy całkowitymi $V1$, $V2$ ze spacją.

• Wiersze $N+2,\ldots,2\times N+1$: wiersz $i-N-1$ zawiera $N$ całkowitych wiersza $i$ macierzy: $Row_{i}$.

Wyjście

• Wiersz $1$: całkowite, minimalny koszt płotu.

Przykład

Wejście 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

Wyjście 1

30

Uwagi

  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

Trzy wyspy to $\{1,7,3,6,10\}$, $\{4,5,11\}$ i $\{2,9,8,12\}$. Koszty daje macierz; z $1$ do $2$ koszt $15$.

Jest więcej rozwiązań. FJ zaczyna w $3$, potem $7$, zatrzymuje się w $1$, płynie do $11$, dalej $4,5,11$. Wraca do $1$, płynie do $12$, dalej $2,9,8,12$. Na koniec wraca do $1$ i kontynuuje $10,6,3,7$. W obie strony z $1$ do $11$ koszt $8 \times 2 = 16$, z $1$ do $12$ $7 \times 2 = 14$, łącznie $30$.

Autor zadania: Fatih Gelgi, 2008