题目描述

老张的农场有 $n$ 块田地，现在需要为所有田地供水。他有两种方式：

1. 在第 $i$ 号田地中打一口井，花费 $W_i$ 元；
2. 在 $i$ 号田地和 $j$ 号田地之间铺设水管，花费 $P_{i,j}$ 元（$P_{i,j}=P_{j,i}$，$P_{i,i}=0$）。

要求每块田地最终都拥有水源（打井的田地直接有水，其他田地通过水管与有水的田地相连即可）。请计算最小总花费。

输入格式

第一行为一个整数 $n$。

接下来 $n$ 行，每行一个整数 $W_i$，表示在第 $i$ 号田地打井的费用。

接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行的第 $j$ 个数表示在 $i$ 号田地和 $j$ 号田地之间铺设水管的费用 $P_{i,j}$。

输出格式

一个整数，表示最小总花费。

样例

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

9

提示

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 300$，$1 \leq W_i \leq 10^5$，$0 \leq P_{i,j} \leq 10^5$。