#P9900. Assignment

    ID: 8122 传统题 2000ms 512MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>CF2200动态规划区间DP前缀和枚举2023“钉耙编程”中国大学生算法设计超级联赛(10)

Assignment

Assignment

Problem Description

You are given two sequences a,ba,b of length nn and a cost matrix AA of size n×nn \times n. The matrix AA satisfies Ai,j≥Ai,j−1\boldsymbol{A_{i,j} \ge A_{i,j-1}} for all 1≤i≤n,1<j≤n1 \le i \le n,1 < j \le n. You can do the following operation arbitrary number of times:

  • Select three integers l,r,xl,r,x satisfying 1≤l≤r≤n1\le l\le r\le n and 1≤x≤n1\le x\le n, then assign xx to aia_i for all indices ii between ll and rr, inclusive. The cost of this operation is Ax,r−l+1A_{x,r-l+1}. For all i∈[0,k]i \in [0,k], find the minimum sum of costs to make aa has at most ii positions differing from bb.

Input

The first line contains a single integer TT (1≤T≤101\le T\le 10), denoting the number of test cases. For each test case, the first line contains two integers n,kn,k (1≤n≤1001\le n\le 100, 1≤k≤101\le k\le 10). The second line contains nn integers a1,a2,⋯ ,ana_1,a_2,\cdots,a_n (1≤ai≤n1 \le a_i \le n), denoting the sequence aa. The third line contains nn integers b1,b2,⋯ ,bnb_1,b_2,\cdots,b_n (1≤bi≤n1 \le b_i \le n), denoting the sequence bb. The next nn lines, each contains nn integers. The jj-th integer in the ii-th line denotes Ai,jA_{i,j} (1≤Ai,j≤1061 \le A_{i,j} \le 10^6). It is guaranteed that for all 1≤i≤n1\le i\le n, 1<j≤n1< j\le n, Ai,j≥Ai,j−1A_{i,j}\ge A_{i,j-1}.

Output

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

Sample Input

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

Sample Output

7 3 1

Source

2023“钉耙编程”中国大学生算法设计超级联赛(10)