题目背景

Atom

题目描述

小Atom有两个长度为 $n$ 的序列 $a$ 和 $b$。其中区间 $[l,r]$，$(1 \leq l \leq r \leq n)$ 的“价值”定义为 $|b_r - a_l|$。

两个区间 $[l_1, r_1]$ $(1 \leq l_1 \leq r_1 \leq n)$ 和 $[l_2, r_2]$ $(1 \leq l_2 \leq r_2 \leq n)$ 不相交，指的是这两个区间满足 $r_1 < l_2$ 或 $r_2 < l_1$。

区间 $[l,r]$ $(1 \leq l \leq r \leq n)$ 的长度定义为 $r - l + 1$。

给定序列 $a$ 和 $b$，小Atom希望找到若干个互不相交、总长度为 $k$ 的区间 $[l,r]$，使得这些区间的价值之和最大。

输入格式

第一行为输入数据总数 $t$。

每组数据共 3 行，第一行是 n,k，第二行是序列 a，第三行是序列 b。

输出格式

对于每组输入数据，输出题干描述的价值总和的最大值。

3
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

0
5
0

提示

$1\le t,\sum n,\sum k\le 400,|a_i|,|b_i|\le 10^8$

有$n^2$做法，有时间可以挑战一下qwq