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

注記

4地あり、井戸は1で5、2と3で4、4で3。管は接続地により2、3、4です。

4に井戸を作り各地を1につなぐと $3+2+2+2=9$ です。

小課題

得点：400

問題作成：Paul Christiano、2007