Description

大家还记得“西南旱灾”吗？我们有多少同胞没有水喝?“干净的水”对他们来说也是种奢望！当大家还在浪费水，洗澡还花上10几分钟，有没有觉得羞愧？西南地区的同胞生活在水深火热之中，yuyan的工程队特意赶到灾区挖井，以缓解旱情。
根据调查，工程队发现有N个地方缺水十分严重！工程队决定在这N个地方选择一些地方挖井，然后在某两个地方之间建立一条运输管道，通过管道把井水传输到其他地方，最后使这N个地方都有水供应！可是，因为地形的差异，每个地方挖水井所要付出的成本是不一定相同的！每两个地方之间建立管道所需要付出的成本也不一定相同。
现在，工程队估算出了每个地方挖井所需要的成本，每两个地方建立运输管道的成本。希望你能告诉他们：在哪些地方挖井，在哪些地方之间建立管道，才能使的总成本最小？同为炎黄子孙，为了广大的受苦同胞，作为中华儿女的你们，有责任去完成这个任务！

Format

Input

一个整数N（1≤N≤300）表示N个地方严重缺水
以下N行，每行一个数，第i行的数为COSTi，表示在编号为i的地方挖水井所需的成本为COSTi
再接着N行，每行N个数，第i行第j个数X
表示在编号为i和编号j之间建造一条管道需要的成本是X
这个N*N的矩阵满足A[i,j]=A[j,i] A[i,i]=0

Output

一个整数，表示使得N个地方都有水的最小成本

Sample 1

Input

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

Output

9

Limitation

1s, 128MB for each test case.

Hint

对于20%的数据：N≤10
对于60%的数据：N≤100
对于100%的数据：N≤300, 所有成本≤100000

在编号为4的地方挖口井，成本为3
在1，2之间建一条管道，成本为2
在1，3之间建一条管道，成本为2
在1，4之间建一条管道，成本为2
至此，这4个地方都直接或间接有水供应，最小成本为3+2+2+2=9

Source

高一年级信息学奥赛模拟考(三)