题目描述

农夫约翰决定给他的N（1<=N<=300）个牧场打水，这些牧场的编号很方便。他可以通过在牧场上打一口井或通过管道将牧场连接到另一个已经有水的牧场来将水引入牧场。
在牧场i挖井的成本为W_i（1<=W_i<=100000）。
连接 i 号田与 j 号田需要 Pij（1≤Pij≤10^5，且 Pji=Pij）元。
请求出 FJ 需要为使所有农场都与有水的农场相连或拥有水井所需要的最少钱数。

输入格式：

第1 行为一个整数n。
第2 到n+1行每行一个整数，从上到下分别为W_1到W_n。
第n+2 到2n+1 行为一个矩阵，表示需要的经费（P_ij）。

输出格式：

只有一行，为一个整数，表示所需要的钱数。

输入样例#1：

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

输出样例#1：

9