多彩的生成树

题目描述

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

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

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

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

输入格式

有多个测试用例。输入的第一行包含一个整数 $T$ ，表示测试用例的数量。对于每个测试用例

第一行包含一个整数 $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}$ 。

保证所有测试用例中 $n$ 的总和不超过 $10^3$ 。

输出格式

针对每个测试用例，输出一行包含一个整数的数据，表示最小生成树的总权重。

样例 #1

样例输入 #1

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

样例输出 #1

102
5
0