Coding is the closest thing we have to superpower !

3270 : 图进阶-挖井人
描述

约翰的农场缺水了,于是他决定将水引入到他的 n 个牧场。

他准备挖若干井,并在各块田中修筑水道来连通各块田地以供水。在第 i 号田中挖一口井需要花费 w_i 元。连接 i 号田与 j 号田需要 P_{i,j} 元,数据保证P_{i,j}=P_{j,i}

请求出约翰所需要的最少钱数,以保证每块田要么有井,要么与有井的田地相连。

输入

第一行为一个整数 n。

接下来 n 行,每行一个整数w_i

接下来 n 行,每行n个整数,第 i 行的第 j 个数表示连接 i 号田和 j 号田需要的费用  P_{i,j}​。

对于 100% 的数据,1 ≤ n ≤ 300,1 ≤ w_i ≤ 10^5,0 ≤ P_{i,j} ≤10^5

输出

输出最小开销。

样例

输入

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

输出

9
标签
语言:
主题: