發(fā)展采礦業(yè)當然首先得有礦井，小 F 花了上次探險獲得的千分之一的財富請人在島上挖了 n 口礦井，但他似乎忘記考慮的礦井供電問題……

為了保證電力的供應(yīng)，小 F 想到了兩種辦法：

在這一口礦井上建立一個發(fā)電站，費用為 v（發(fā)電站的輸出功率可以供給任意多個礦井）。

將這口礦井與另外的已經(jīng)有電力供應(yīng)的礦井之間建立電網(wǎng)，費用為 p。

小 F 希望身為「NewBe_One」計劃首席工程師的你幫他想出一個保證所有礦井電力供應(yīng)的最小花費。

第一行一個整數(shù) n，表示礦井總數(shù)。

第 2～n+1行，每行一個整數(shù)，第 i 個數(shù) v_i 表示在第 i 口礦井上建立發(fā)電站的費用。

接下來為一個 n×n 的矩陣 p，其中 p_i,j 表示在第 i 口礦井和第 j 口礦井之間建立電網(wǎng)的費用（數(shù)據(jù)保證有p_i,j=p_j,i ，且 p_i,i=0。

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

9

樣例解釋

小 F 可以選擇在 4 號礦井建立發(fā)電站然后把所有礦井都不其建立電網(wǎng)，總花費是 3+2+2+2=9。

數(shù)據(jù)范圍:

對于 30% 的數(shù)據(jù)：1≤n≤50；

對于 100% 的數(shù)據(jù)：1≤n≤300,0≤v_i,p_i,j≤10⁵ 。