Assignment

You are given two sequences $a,b$ of length $n$ and a cost matrix $A$ of size $n \times n$. The matrix $A$ satisfies $A_{i,j} \geq A_{i,j-1}$ for all $1 \leq i \leq n$, $1 < j \leq n$. You can do the following operation arbitrary number of times:

• Select three integers $l,r,x$ satisfying $1 \leq l \leq r \leq n$ and $1 \leq x \leq n$, then assign $x$ to $a_i$ for all indices $i$ between $l$ and $r$, inclusive. The cost of this operation is $A_{x,r-l+1}$.

For all $i \in [0,k]$, find the minimum sum of costs to make $a$ has at most $i$ positions differing from $b$.

Input

The first line contains a single integer $T \: (1 \leq T \leq 10)$, denoting the number of test cases.

For each test case, the first line contains two integers $n, k \: (1 \leq n \leq 100, 1 \leq k \leq 10)$.

The second line contains $n$ integers $a_1, a_2, \dots , a_n \: (1 \leq a_i \leq n)$, denoting the sequence $a$.

The third line contains $n$ integers $b_1,b_2,\dots,b_n(1 \leq b_i \leq n)$, denoting the sequence $b$.

The next $n$ lines, each contains $n$ integers. The $j$-th integer in the $i$-th line denotes $A_{i,j} \: (1 \leq A_{i,j} \leq 10^6)$.

It is guaranteed that for all $1 \leq i \leq n, 1 < j \leq n, A_{i,j} \geq A_{i,j-1}$.

Output

For each test case, output one line with $k + 1$ integers denoting the answer

Example

1
5 2
1 5 3 2 2
2 4 5 4 2
3 3 3 4 4
2 2 3 4 5
3 4 5 6 7
1 1 1 2 4
4 5 5 5 5

7 3 1