Farmer John은 목초지 $N$개($1 \le N \le 300$), 번호 $1,\ldots,N$에 물을 공급한다. 해당 목초지에 우물을 짓거나 물이 있는 다른 목초지에 관으로 연결한다.

$i$의 우물은 $W_i$($1 \le W_i \le 100,000$), $i$, $j$를 연결하는 관은 $P_{ij}$($1 \le P_{ij} \le 100,000; P_{ij}=P_{ji}; P_{ii}=0$)이다.

모든 목초지에 물을 공급할 최소 비용을 구하라.

입력

• 1번째 줄: 정수 $N$.
• $2,\ldots,N+1$번째 줄: $i+1$번째 줄에 정수 $W_i$.
• $N+2,\ldots,2N+1$번째 줄: $N+1+i$번째 줄에 공백으로 구분한 정수 $N$개, $j$번째가 $P_{ij}$.

출력

• 1번째 줄: 모든 목초지 물 공급의 최소 비용인 정수.

예제

입력 1

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

출력 1

9

참고

목초지 네 개에서 우물은 1번에 5, 2와 3번에 4, 4번에 3이다. 관은 연결 목초지에 따라 2, 3, 4이다.

4번에 우물을 짓고 각 목초지를 1번에 연결하면 $3+2+2+2=9$이다.

서브태스크

점수: 400

문제 작성: Paul Christiano, 2007