问题 B: 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 ��,�≥��,�−1Ai,j≥Ai,j−1 for all $1\le i\le n,1<j\le n$. You can do the following operation arbitrary number of times:

• Select three integers $l,r,x$ satisfying $1\le l\le r\le n$ and $1\le x\le n$, then assign $x$ to ��ai for all indices $i$ between $l$ and $r$, inclusive. The cost of this operation is ��,�−�+1Ax,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$.

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

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

The second line contains $n$ integers �1,�2,⋯,��a1,a2,⋯,an (1≤��≤�1≤ai≤n), denoting the sequence $a$.

The third line contains $n$ integers �1,�2,⋯,��b1,b2,⋯,bn (1≤��≤�1≤bi≤n), denoting the sequence $b$.

The next $n$ lines, each contains $n$ integers. The $j$-th integer in the $i$-th line denotes ��,�Ai,j (1≤��,�≤1061≤Ai,j≤106).

It is guaranteed that for all $1\le i\le n$, $1<j\le n$, ��,�≥��,�−1Ai,j≥Ai,j−1.

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