题目描述

N 块田地遭遇旱灾，急需浇灌。

一块田地要想得到浇灌，可以在该块田地上钻井取水，也可以从其他得到浇灌的田地引水过来。

我们将这些田地从 1 ~ N 进行编号。

在 i 号田地钻井取水需要付出的代价为 $S_i$。

在 i 号田地和 j 号田地之间引水需要付出的代价为 $T_{i,j}$。（$T_{j,i}=T_{i,j}$）

问：要让所有田地都得到灌溉，需要付出的最小总代价是多少？

输入格式

第一行：包含一个整数 $N$；

接下来 $N$ 行，每行包含一个整数 $S_i$；

接下来是一个 $N×N$ 的整数矩阵 $T$，其中第 $i$ 行第 $j$ 的数 $T_{i,j}$ 表示在 $i$ 号田地和 $j$ 号田地之间引水的代价。数据保证 $T_{j,i}=T_{i,j}$。

输出格式

一个整数，表示答案。

样例输入

3
4
5
6
0 1 2
1 0 3
2 3 0

样例输出

7

提示

20% 的数据：$1 ≤ N ≤ 10$；

70% 的数据：$1 ≤ N ≤ 100$；

100% 的数据：$1 ≤ N ≤ 300$，$1 ≤ S_i ≤ 10^5$，$0 ≤ T_{i,j} = T_{j,i} ≤ 10^5$。