Farmer John mua đất ở Caribe và định nuôi bò sữa tại trang trại lớn gồm các đảo. Theo thói quen, ông muốn rào tất cả đảo.

Mỗi đảo là đa giác. Ông rào từng cạnh giữa hai đỉnh liên tiếp, theo chiều kim đồng hồ. Để rào hết, có lúc phải đi thuyền sang đảo khác.

Có thể bắt đầu ở bất kỳ đỉnh nào, và ở mỗi đỉnh gặp phải đi sang đỉnh đảo khác, rào toàn bộ đảo đó rồi lập tức trở về cùng đỉnh đảo gốc bằng cùng đường đã đi. Mỗi chuyến thuyền có chi phí theo ma trận cho sẵn.

Các đảo mô tả bởi $N$ $(3 \le N \le 500)$ cặp đỉnh $V1$,$V2$ $(1 \le V1 \le N; 1 \le V2 \le N)$; bạn tự xác định cách ghép thành đảo. Đỉnh đánh số $1,\ldots,N$.

Ma trận đối xứng có phần tử $0,\ldots,1000$ cho chi phí thuyền giữa mỗi cặp đỉnh.

Chi phí nhỏ nhất để rào toàn bộ đảo là bao nhiêu?

Dữ liệu vào

• Dòng $1$: số nguyên $N$.

• Dòng $2,\ldots,N+1$: mỗi dòng mô tả biên đảo bằng số nguyên $V1$, $V2$ cách bởi dấu cách.

• Dòng $N+2,\ldots,2\times N+1$: dòng $i-N-1$ chứa $N$ số nguyên của hàng $i$ ma trận: $Row_{i}$.

Dữ liệu ra

• Dòng $1$: số nguyên, chi phí xây rào nhỏ nhất.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

30

Ghi chú

  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

Ba đảo là $\{1,7,3,6,10\}$, $\{4,5,11\}$, $\{2,9,8,12\}$. Ma trận cho phí; từ $1$ đến $2$ là $15$.

Có nhiều lời giải. FJ từ $3$ qua $7$ dừng ở $1$, đi đến $11$ rồi $4,5,11$. Trở về $1$, đến $12$ rồi $2,9,8,12$. Cuối cùng về $1$ tiếp $10,6,3,7$. Khứ hồi $1$ đến $11$ tốn $8 \times 2 = 16$, $1$ đến $12$ $7 \times 2 = 14$, tổng $30$.

Tác giả bài toán: Fatih Gelgi, 2008