分配

中文题目为机翻，原题目请参考英文题面

给您两个长度为 $n$ 的序列 $a,b$，以及一个大小为 $n \times n$ 的成本矩阵 $A$。矩阵 $A$ 满足 $A_{i,j} \geq A_{i,j-1}$ 对于所有的 $1 \leq i \leq n$, $1 < j \leq n$. 你可以任意多次进行下面的操作：

• 选择三个整数 $l,r,x$ 满足 $1 \leq l \leq r \leq n$ 和 $1 \leq x \leq n$，然后为 $l$ 和 $r$ 之间的所有索引 $i$ 赋值 $x$ 到 $a_i$。这个操作的代价是 $A_{x,r-l+1}$。

对于 $[0,k]$ 中的所有 $i$，求使 $a$ 与 $b$ 最多相差 $i$ 位置的最小成本总和。

输入

第一行包含一个整数 $T \: (1 \leq T \leq 10)$，表示测试案例的数量。

对于每个测试用例，第一行包含两个整数 $n, k \:(1 \leq n \leq 100, 1 \leq k \leq 10)$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots , a_n \: (1 \leq a_i \leq n)$，表示序列 $a$。

第三行包含 $n$ 整数 $b_1,b_2,\dots,b_n(1\leq b_i \leq n)$，表示序列 $b$。

接下来的 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行中的第 $j$ 个整数表示 $A_{i,j} \: (1 \leq A_{i,j} \leq 10^6)$。

可以保证，对于所有的 $1 \leq i \leq n, 1 < j \leq n, A_{i,j} \geq A_{i,j-1}$。

输出

对于每个测试用例，输出一行，用 $k + 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