워터링 홀

농부 존은 N (1 <= N <= 300) 개의 풀밭에 물을 공급하기로 결정했고, 이 때 풀밭들은 편리하게 1..N 까지로 번호가 매겨져 있다. 그는 풀밭에 우물을 파는 것이나, 이미 물이 공급된 다른 풀밭과 파이프로 연결하여 물을 공급할 수 있다.

풀밭 i에 우물을 파는 데는 W_i (1 <= W_i <= 100,000)의 비용이 든다. 풀밭 i와 j를 파이프로 연결하는 데는 P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0)의 비용이 든다.

농부 존이 모든 풀밭에 물을 공급하기 위해 지불해야 할 최소비용을 정하시오.

• 1번째 줄: 하나의 정수: N
• 2번째 줄 ~ N+1번째 줄: i+1 번째 줄은 하나의 정수를 포함합니다: W_i
• N+2번째 줄 ~ 2N + 1번째 줄: N+1 + i 번째 줄은 N개의 공백으로 구분된 정수를 포함하며, j번째 정수는 P_ij입니다.

• 1번째 줄: 모든 풀밭에 물을 공급하는데 필요한 최소비용인 하나의 정수를 포함하는 단일 줄