给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个长度为 $$$n$$$ 的数组 $$$b$$$。段 $$$[l, r]$$$, $$$1 \le l \le r \le n$$$ 的成本定义为 $$$|b_l - a_r| + |b_r - a_l|$$$。
回想一下,如果满足以下条件之一,则两条线段 $$$[l_1, r_1]$$$、$$$1 \le l_1 \le r_1 \le n$$$ 和 $$$[l_2, r_2]$$$、$$$1 \le l_2 \le r_2 \le n$$$ 是不相交的: $$$r_1 < l_2$$$ 或 $$$r_2 < l_1$$$。
段 $$$[l, r]$$$, $$$1 \le l \le r \le n$$$ 的长度定义为 $$$r - l + 1$$$。
求非相交线段 $$$[l_j, r_j]$$$, $$$1 \le l_j \le r_j \le n$$$ 的最大可能成本总和,其总长度等于 $$$k$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 1000)$$$ — 输入数据的组数。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 3000$$$) — 数组 $$$a$$$ 的长度和段的总长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — 数组 $$$b$$$ 的元素。
保证所有测试用例的$$$n$$$总和不超过$$$3000$$$。
输出
对于每个测试用例,输出一个数字 - 这些段的最大可能成本总和。
示例
输入 #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
注意
在第一个测试用例中,任何段的成本都是 $$$0$$$,因此总成本是 $$$0$$$。
在第二个测试用例中,我们可以采用成本为 $$$8$$$ 的段 $$$[1, 1]$$$ 和成本为 $$$2$$$ 的段 $$$[3, 3]$$$ 来获得总和 $$$10$$$。可以证明这是最优解。
在第三个测试用例中,我们只对长度为 $$$1$$$ 的段感兴趣,并且任何此类段的成本为 $$$0$$$。
在第四个测试用例中,可以证明最优总和是$$$16$$$。例如,我们可以采用段 $$$[3, 3]$$$ 和 $$$[4, 4]$$$。