最大单角性

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定两个长度均为 $n$ 的整数序列 $a,b$。区间 $[l,r]$ 的价值定义为

你需要选出若干个两两不相交的非空区间，使所选区间的长度之和恰好为 $k$。求所选区间价值之和的最大值。

两个区间 $[l_1,r_1]$ 和 $[l_2,r_2]$ 不相交，当且仅当 $r_1<l_2$ 或 $r_2<l_1$。

输入格式

第一行一个整数 $t$，表示测试数据组数。

每组数据包含三行：

• 第一行两个整数 $n,k$；
• 第二行 $n$ 个整数 $a_1,ldots,a_n$；
• 第三行 $n$ 个整数 $b_1,ldots,b_n$。

输出格式

对每组数据输出一行，表示最大价值和。

样例输入 1

5
4 4
1 1 1 1
1 1 1 1
3 2
1 3 2
5 2 3
5 1
1 2 3 4 5
1 2 3 4 5
7 2
1 3 7 6 4 7 2
1 5 3 2 7 4 5
4 2
17 3 5 8
16 2 5 9

样例输出 1

0
10
0
16
28

数据范围

对所有数据：

• $1\le t\le1000$；
• $1\le k\le n\le3000$；
• 单个输入中所有测试数据的 $n$ 之和不超过 $3000$；
• $-10^9\le a_i,b_i\le10^9$。

计分方式

本题按测试点独立计分，每个测试点的分值与其所属子任务表中分值合计一致。