J. Colorful Spanning Tree
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

BaoBao has many colored vertices. The colors are numbered from $$$1$$$ to $$$n$$$ (both inclusive), and there are $$$a_i$$$ vertices of color $$$i$$$. As BaoBao has just learnt the minimum spanning tree problem in his algorithm class, he decides to practice it with the vertices.

Each pair of vertices is connected by an weighted edge. The weight of each edge is only related to the colors of its two endpoints. More precisely, let $$$c_u$$$ be the color of vertex $$$u$$$, if an edge connects vertices $$$u$$$ and $$$v$$$, its weight will be $$$b_{c_u, c_v}$$$.

Help BaoBao calculate the total weight of the minimum spanning tree of the graph.

Recall that a minimum spanning tree is a subset of the edges in a connected, weighted graph that connects all the vertices without any cycles and with the minimum possible total weight.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^3$$$) indicating the number of different colors.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le 10^6$$$), where $$$a_i$$$ is the number of vertices with color $$$i$$$.

For the following $$$n$$$ lines, the $$$i$$$-th line contains $$$n$$$ integers $$$b_{i, 1}, b_{i, 2}, \cdots, b_{i, n}$$$ ($$$1 \le b_{i, j} \le 10^6$$$) where $$$b_{i, j}$$$ is the weight of an edge connecting two vertices with color $$$i$$$ and $$$j$$$. It's guaranteed that $$$b_{i, j} = b_{j, i}$$$ for all $$$1 \le i, j \le n$$$.

It's guaranteed that the sum of $$$n$$$ over all the test cases doesn't exceed $$$10^3$$$.

Output

For each test case, output one line containing one integer, indicating the total weight of the minimum spanning tree.

Example
Input
3
3
100 1 1
1 100 2
100 100 1
2 1 100
2
3 3
100 1
1 100
1
1
5
Output
102
5
0