题目描述

一共有$n$个城市，现在要给这$n$个城市提供石油。

在每个城市挖油井采矿的成本各不相同，在第$i$个城市打一口油井需要$w_i$的成本。当然，还可以通过建立运输管道来提供石油，城市$x$和城市$y$之间建立管道的成本为$P_{xy}$。如果某个没有油井的城市$a$，通过多条管道能连接到油井，那么城市$a$也会有石油供应。

现在给每个城市都提供石油，求最小总成本。

输入格式

第一行有一个整数$n$，表示城市个数；

接下来$n$行，每行输入一个整数$w_i$；

再接下来$n$行，每行输入$n$个空格隔开的整数$P_{xy}$，数据保证$P_{xy}==P_{yx}$。

输出格式

使得每个城市都有石油的最小总成本。

样例

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

9

提示

样例1解释

在城市4处挖一口油井，城市1和城市4建立管道，城市1和城市2建立管道，城市1和城市3建立管道，总成本为9.

数据范围

$1\le n \le 300$，$1\le w_i \le 10^5$，$1\le P_{xy} \le 10^5$（对于不同的 $x$ 和 $y$）。