给定两个长度为 $n$ 的序列 $a, b$ 以及一个大小为 $n \times n$ 的代价矩阵 $A$。矩阵 $A$ 满足对于所有 $1 \le i \le n, 1 < j \le n$，都有 $A_{i,j} \ge A_{i,j-1}$。你可以进行任意次数的以下操作：

• 选择三个整数 $l, r, x$，满足 $1 \le l \le r \le n$ 且 $1 \le x \le n$，然后将 $a_i$ 赋值为 $x$，对于所有 $l$ 到 $r$ 之间的下标 $i$（包含 $l$ 和 $r$）。该操作的代价为 $A_{x, r-l+1}$。

对于所有 $i \in [0, k]$，求出使得 $a$ 与 $b$ 不同的位置数不超过 $i$ 的最小总代价。

输入格式

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

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

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

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

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

保证对于所有 $1 \le i \le n, 1 < j \le n$，有 $A_{i,j} \ge A_{i,j-1}$。

输出格式

对于每个测试用例，输出一行，包含 $k+1$ 个整数，表示答案。

样例

输入 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

输出 1

7 3 1