Farmer John은 카리브해 땅을 사서 섬들로 된 큰 농장에서 젖소를 기르려 한다. 습관대로 모든 섬을 울타리로 둘러싸고 싶다.

각 섬은 다각형이다. 연속 꼭짓점 사이 한 변씩 시계 방향으로 울타리를 친다. 모든 섬을 위해 어느 시점에는 배로 다른 섬에 가야 한다.

어느 꼭짓점에서든 시작하며, 만나는 어느 꼭짓점에서든 다른 섬 꼭짓점으로 가서 그 섬 전체를 둘러싼 뒤 즉시 같은 경로로 원래 섬의 같은 꼭짓점에 돌아온다. 각 배 이동 비용은 행렬로 주어진다.

섬은 $N$ $(3 \le N \le 500)$개 꼭짓점 쌍 $V1$,$V2$ $(1 \le V1 \le N; 1 \le V2 \le N)$로 표현되며 어떻게 섬을 이루는지 알아내야 한다. 꼭짓점 번호는 $1,\ldots,N$이다.

각 꼭짓점 쌍의 배 비용은 원소가 $0,\ldots,1000$인 대칭 행렬이다.

모든 섬에 울타리를 치는 최소 비용은 얼마인가?

입력

• $1$번째 줄: 정수 $N$.

• $2,\ldots,N+1$번째 줄: 각 줄은 공백 구분 정수 $V1$, $V2$로 섬 경계를 설명한다.

• $N+2,\ldots,2\times N+1$번째 줄: $i-N-1$번째 줄에 행렬 $i$번째 행 $Row_{i}$를 설명하는 $N$ 정수.

출력

• $1$번째 줄: 최소 울타리 비용 정수.

예제

입력 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

출력 1

30

참고

  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$에서 $2$는 $15$다.

해는 여러 개다. FJ는 $3$, $7$을 거쳐 $1$에 멈추고 $11$로 이동해 $4,5,11$을 지난다. $1$로 돌아와 $12$로 가서 $2,9,8,12$를 지난다. 마지막에 $1$로 돌아와 $10,6,3,7$을 계속한다. $1$에서 $11$ 왕복은 $8 \times 2 = 16$, $1$에서 $12$ 왕복은 $7 \times 2 = 14$, 합 $30$이다.

문제 출제: Fatih Gelgi, 2008