Announcement
**Second Round will be ONLINE instead of ONSITE*****
Problem Statement

Dora bought n paint buckets (numbered as 0,1,2,...,n-1) of k distinct colors with Ci as the color of ith bucket. She arranges the buckets in a straight line according to their number in ascending order. She wants to mix all the paint buckets but in a very special way. ith paint bucket can be mixed only with either (i+1)th or (i-1)th bucket.

(a) If ith bucket is mixed with (i-1)th bucket the resulting number of the mixture will be i-1.The no on the buckets placed at (i+1)th,(i+2)th,...,(n-1)th will be decreased by 1.

(b) If ith bucket is mixed with (i+1)th bucket the resulting number of the mixture will be i.The no of the buckets placed at (i+2)th,(i+3)th...,(n-1)th will be decreased by 1.

She will continue mixing the paint until one bucket is left and no further mixing can be done.

Every such mixing requires some fixed no of seconds so that the paint get mixed thoroughly. T is a k x k matrix in which T(i,j) tells us how much seconds it take to mix the paint of colors i and j.

If ith bucket with color Ci is mixed with jth bucket of Color Cj, the resultant color will be (Ci+Cj)mod(k) and time taken will be T(Ci,Cj).
See sample case for more explanation.

Dora wants to mix all the paint buckets in minimum possible time. Calculate the minimum possible time required for this task.

Input

First line contains t, no. of testcases.

First line of each test case contains two space separated integers n and k. Next line contains n space separated integers C0 C1 C2 ... Cn-1 , the color of the n paint buckets.

Next k lines contains the rows for matrix T with each line containing k space separated integers. jth integer in the ith line is the time in seconds Dora takes to mix colours i and j.

Output

The minimum possible time(in seconds) she takes, to mix all the colors.

Constraints

1 ≤ t ≤ 10

1 ≤ n ≤ 100

1 ≤ k ≤ 100

0 ≤ Ci ≤ k-1

1 ≤ Tij ≤ 10000

Note: Mixing ith color with jth color is same as mixing jth color with ith color.

SAMPLE INPUT
2
3 3
0 1 1
1 2 1
2 2 1
1 1 2
3 3
0 1 2
1 2 1
2 2 1
1 1 2

SAMPLE OUTPUT
3
2

Explanation

In the first case, she will mix bucket numbered 1 and 2 holding color 1 and 1 respectively. The resultant color is 2 ( (1+1)%3 ) and time taken for this process is 2 seconds. As 1st and 2nd bucket are mixed, the number of the mixture will be 1.
Now 0th bucket and 1st bucket (newly obtained bucket) will be mixed giving a paint bucket of color 2 ( (0+2)%3 )and time taken for this process is 1 second.
Total time is 2+1=3 seconds.

Similarly for the second case.

见题面

见题面