天然气 1835

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：15 AC：4 Score：100

Description

我们知道天然气是一种非常清洁的能源，我国打算普及天然气。

我国一共有 $n$ 个城市，现在要给这 $n$ 个城市通天然气。在每个城市打井通气的成本不一样，在第 $i$ 个城市打一口天然气井需要 $w_i$ 的成本。当然，每个城市通天然气不仅仅只能通过打井通天然气，还可以通过建立天然气运输管的方式通气。在城市 $i$ 和城市 $j$ 之间建立天然气管道的成本为 $p_{ij}$。如果某个有井的城市通过一系列管道能把天然气运输到城市 $x$，那么城市 $x$ 也可以通气。

现在要让每个城市都要通气，请你求出最小成本总和是多少。

Input

输入第一行一个整数 $n(1 \le n \le 300)$，表示城市总数。

接下来 $n$ 行，每行输入一个整数代表 $w_i(1 \le w_i \le 100000)$。

再接下来 $n$ 行，每行输入 $n$ 个空格隔开的整数 $p_{ij}(1 \le p_{ij} \le 100000)$。

Output

输出最小的成本花费。

Samples

input:

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

output: