[Usaco2008 Oct]灌水

Farmer John 决定为他的 $n$ 块农田供水，农田编号为 $1$ 到 $n$。

一块农田可以通过以下两种方式获得水源：

• 在这块农田中修建水库，费用为 $w_i$；
• 修建管道，将这块农田与另一块已经获得水源的农田连接起来，连接农田 $i$ 与农田 $j$ 的费用为 $p_{ij}$。

请计算使所有农田都能获得水源所需的最小总费用。

输入格式

第一行包含一个整数 $n$，表示农田数量。

接下来 $n$ 行，第 $i$ 行包含一个整数 $w_i$，表示在农田 $i$ 中修建水库的费用。

接下来 $n$ 行，每行包含 $n$ 个以空格分隔的整数。其中第 $i$ 行的第 $j$ 个整数为 $p_{ij}$，表示连接农田 $i$ 与农田 $j$ 的费用。

输出格式

输出一个整数，表示使所有农田都能获得水源所需的最小总费用。

样例输入

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

样例输出

9

样例解释

在编号为 $4$ 的农田中修建水库，将农田 $1$ 与农田 $4$ 连接，再将农田 $2$、农田 $3$ 分别与农田 $1$ 连接，总费用为

$$3+2+2+2=9。$$

数据范围

• $1\le n\le 300$；
• $1\le w_i\le 10^5$；
• $1\le p_{ij}\le 10^5$，其中 $i\ne j$；
• $p_{ij}=p_{ji}$，且 $p_{ii}=0$。

来源与许可

本题为 USACO 2008 October 试题「灌水」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

9