题目描述

堡堡有很多彩色的节点。颜色的编号从 $1$ 到 $n$（含两端），第 $i$ 种颜色共有 $a_i$ 个节点。因为堡堡刚刚在算法课上学习了最小生成树问题，他打算利用这些节点做一些练习。

每一对节点都会被一条带有权值的边连接。每一条边的权值只和它两个端点的颜色有关。具体来说，令 $c_u$ 表示节点 $u$ 的颜色，若一条边连接了节点 $u$ 和 $v$，它的权值就是 $b_{c_u, c_v}$。

请帮助堡堡求出这张图的最小生成树的总权值。

请回忆：最小生成树是一张带权连通图的边的子集，这些边连通了所有节点，不会形成环，且总权值最小。

输入格式

有多组测试数据。第一行输入一个整数 $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$。

输出格式

每组数据输出一行一个整数，表示最小生成树的总权值。

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

102
5
0