You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小明有许多彩色顶点。颜色从 $1$ 到 $n$ （都包括在内），颜色为 $i$ 的顶点有 $a_i$ 个。小宝刚在算法课上学习了最小生成树问题，他决定用这些顶点来练习一下。

每对顶点由一条加权边连接。每条边的权重只与其两个端点的颜色有关。更确切地说，假设 $c_u$ 是顶点 $u$ 的颜色，如果一条边连接了顶点 $u$ 和 $v$ ，那么它的权重就是 $b_{c_u, c_v}$ 。

请帮助小宝计算图中最小生成树的总权重。

回顾一下，最小生成树是连接加权图中的一个边的子集，它连接所有顶点，没有任何循环，并且总权重尽可能小。

输入格式

第一行包含一个整数 $n$ ( $1 \le n \le 10^3$ )，表示不同颜色的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ( $1 \le a_i \le 10^6$ )，其中 $a_i$ 是颜色为 $i$ 的顶点个数。

在接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $b_{i, 1}, b_{i, 2}, \cdots, b_{i, n}$ ( $1 \le b_{i, j} \le 10^6$ )，其中 $b_{i, j}$ 是连接颜色为 $i$ 和 $j$ 的两个顶点的边的权重。可以保证所有 $1 \le i, j \le n$ 都是 $b_{i, j} = b_{j, i}$ 。

输出格式

输出一行包含一个整数，表示最小生成树的总权。

样例1

输入

3
100 1 1
1 100 2
100 100 1
2 1 100

输出

102

样例2

输入

2
3 3
100 1
1 100

输出

5

样例解释

对于第一个样例，颜色$1$：$100$个顶点，颜色$2$：$1$个顶点，颜色$3$：$1$个顶点 颜色$1$内部边权为$1$,颜色$2$内部边权为$100$,颜色$3$内部边权为$100$。 颜色$1$和颜色$2$之间的最小边权为$100$，颜色$1$和颜色3之间的最小边权为$2$，颜色$2$和颜色$3$之间的最小边权为$1$

颜色$1$的$100$个顶点通过内部边权$1$连接，总权为$100-1=99$ 颜色$2$的$1$个顶点通过边权$1$连接到颜色3的顶点 颜色$3$的顶点通过边权$2$连接到颜色$1$的某个顶点 总和：$99 + 1 + 2 = 102$

数据分布

$40 \%$ 的样例，$1 \le n \le 10$，$1 \le a_i \le 100$，$1 \le b_{i, j} \le 100$

$100 \%$ 的样例，$1 \le n \le 10^3$，$1 \le a_i \le 10^6$，$1 \le b_{i, j} \le 10^6$

时空限制

• 时间限制：$2s$
• 空间限制：$512M$