BaoBao 有许多带颜色的顶点。颜色编号从 $1$ 到 $n$（包含 $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, \dots, a_n$ ($1 \le a_i \le 10^6$)，其中 $a_i$ 是颜色为 $i$ 的顶点数量。

接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $b_{i,1}, b_{i,2}, \dots, 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

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