논에 물 대기

농부는 자신이 운영하는 N개의 논 모두에 물을 공급하려고 한다. 물을 공급하는 방법은 두 가지이다. 어떤 논에는 직접 우물을 팔 수 있고, 이미 물이 공급되는 다른 논에서 물길을 연결해 물을 끌어올 수도 있다.

각 논에 우물을 파는 비용과 두 논 사이에 물길을 연결하는 비용이 주어진다. 모든 논에 물을 공급하는 데 필요한 최소 비용을 구하라.

첫째 줄에 논의 수 N이 주어진다.

다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi가 순서대로 주어진다.

그다음 N개의 줄에는 각 줄마다 N개의 정수가 주어진다. i번째 줄의 j번째 수 Pi,j는 i번째 논과 j번째 논을 물길로 연결하는 비용이다.

조건은 다음과 같다.

• 1 ≤ N ≤ 300
• 1 ≤ Wi ≤ 100,000
• 1 ≤ Pi,j ≤ 100,000 (i ≠ j)
• Pi,j = Pj,i
• Pi,i = 0

모든 논에 물을 공급하는 데 필요한 최소 비용을 출력한다.