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