[USACO08OCT]打井Watering Hole

题目背景

John的农场缺水了!!!

题目描述

Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water. Digging a well in pasture i costs W\_i (1 <= W\_i <= 100,000). Connecting pastures i and j with a pipe costs P\_ij (1 <= P\_ij <= 100,000; P\_ij = P\_ji; P\_ii=0). Determine the minimum amount Farmer John will have to pay to water all of his pastures. POINTS: 400 农民John 决定将水引入到他的n(1<=n<=300)个牧场。他准备通过挖若 干井,并在各块田中修筑水道来连通各块田地以供水。在第i 号田中挖一口井需要花费W\_i(1<=W\_i<=100,000)元。连接i 号田与j 号田需要P\_ij (1 <= P\_ij <= 100,000 , P\_ji=P\_ij)元。 请求出农民John 需要为使所有农场都与有水的农场相连或拥有水井所需要的钱数。

输入输出格式

输入格式


第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

说明

John等着用水,你只有1s时间!!!