该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

农场主有 $N$ 块田地。要让所有农田都有水灌溉，有两种方法：

1. 挖井：在第 $i$ 块田地自己挖一口井，花费为 $W_i$。
2. 修渠：从已经有水的第 $j$ 块田修一条水渠到第 $i$ 块田，花费为 $P_{ij}$。 只要一块田地有水（要么自己挖了井，要么通过水渠连到了其他有水的田），它就被认为是可以灌溉的。 请计算让所有农田都被灌溉的最小总费用。

输入格式

第一行一个整数 $N$。 接下来 $N$ 行，每行一个整数 $W_i$，表示第 $i$ 块田挖井的费用。 接下来一个 $N \times N$ 的矩阵，第 $i$ 行第 $j$ 列的整数表示 $P_{ij}$（即连接田地 $i$ 和田地 $j$ 的费用）。 数据保证 $P_{ij} = P_{ji}$，且 $P_{ii} = 0$。

输出格式

输出一个整数，表示最小总费用。

输入输出样例 #1

输入 #1

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

输出 #1

9

数据范围

对于 $100\%$ 的数据， $1 \le N \le 300$， $1 \le W_i, P_{ij} \le 100000$。