섬 둘레에 울타리 치기

문제

농부 존이 여러 개의 섬으로 이루어진 큰 농장을 사서 젖소를 키우려 한다. 그는 모든 섬의 둘레에 울타리를 치고 싶어 한다.

각 섬은 다각형 모양이다. 존은 한 섬을 시계 방향으로 돌면서 이웃한 두 꼭짓점 사이를 한 변씩 울타리로 잇는다. 한 섬의 둘레를 걸어서 도는 데에는 비용이 들지 않는다.

모든 섬에 울타리를 치려면 배를 타고 다른 섬으로 건너가야 한다. 존은 아무 꼭짓점에서나 울타리 치기를 시작할 수 있고, 지나는 임의의 꼭짓점에서 배를 타고 다른 섬의 어떤 꼭짓점으로 건너가 그 섬의 둘레를 전부 울타리로 두른 뒤, 갔던 경로를 그대로 되짚어 곧바로 원래 섬의 같은 꼭짓점으로 돌아온다. 즉 한 번의 배 왕복에는 편도 뱃삯의 두 배가 든다.

꼭짓점 쌍 사이를 배로 오가는 비용은 대칭인 비용 행렬로 주어진다.

섬은 $N$개의 꼭짓점 쌍 $(V_1, V_2)$로 주어지며, 이 변들을 어떻게 섬으로 조립할지는 스스로 알아내야 한다. 꼭짓점은 $1$부터 $N$까지 번호가 매겨져 있고, 각 꼭짓점은 정확히 하나의 섬에 속한다.

모든 섬을 울타리로 둘러싸는 데 드는 최소 비용을 구하여라.

제약: $3 \le N \le 500$, $1 \le V_1, V_2 \le N$, 각 배 이동 비용은 $0$ 이상 $1000$ 이하.

입력

첫째 줄: 정수 $N$.
둘째 줄부터 $N+1$째 줄까지: 각 줄에 섬 둘레의 한 변을 이루는 두 꼭짓점 $V_1$, $V_2$가 공백으로 구분되어 주어진다.
$N+2$째 줄부터 $2N+1$째 줄까지: 비용 행렬의 각 행. $i$번째 줄에는 $N$개의 정수가 있으며, 꼭짓점 $i$에서 다른 각 꼭짓점으로 배를 타고 이동하는 비용을 뜻한다. 행렬은 대칭이다.

출력

모든 섬에 울타리를 치는 최소 비용을 정수 하나로 출력한다.

힌트

아래 그림은 세 개의 섬을 나타낸다.

  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

세 섬은 각각 꼭짓점 ${1,7,3,6,10}$, ${4,5,11}$, ${2,9,8,12}$로 이루어진다.

예를 들어 존이 꼭짓점 $1$에서 배를 타고 꼭짓점 $11$로 건너가 둘째 섬을 두르고 다시 $1$로 돌아오면 $8 \times 2 = 16$이 들고, $1$에서 $12$로 건너가 셋째 섬을 두르고 돌아오면 $7 \times 2 = 14$가 든다. 첫째 섬은 시작 섬이라 배를 탈 필요가 없으므로, 총비용은 $16 + 14 = 30$이다. 최적해는 여러 가지일 수 있다.