发展采矿业当然首先得有矿井,小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 n 口矿井,但他似乎忘记考虑的矿井供电问题……
为了保证电力的供应,小 FF 想到了两种办法:
小 FF 希望身为「NewBe_One」计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。
第一行一个整数 n ,表示矿井总数。
第 2\sim n+1 行,每行一个整数,第 i 个数 v_i 表示在第 i 口矿井上建立发电站的费用。
接下来为一个 n\times n 的矩阵 p ,其中 p_{i,j} 表示在第 i 口矿井和第 j 口矿井之间建立电网的费用(数据保证有 p_{i,j}=p_{j,i} ,且 p_{i,i}=0 )。
输出仅一个整数,表示让所有矿井获得充足电能的最小花费。
4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0
9
小 FF 可以选择在 4 号矿井建立发电站然后把所有矿井都不其建立电网,总花费是 3+2+2+2=9 。
对于 30\% 的数据: 1\le n\le50 ; 对于 100\% 的数据: 1\le n\le 300,0\le v_i, p_{i,j}\le 10^5 。