CF1859E Maximum Monogonosity

有两个长度为 $n$ 的序列 $a$，$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$。 给定 $a,b$，求若干个**互不相交的，总长度为 $k$ 的** $[l,r]$ 的价值总和的最大值。

第一行为输入数据总数 $t$。 每组数据共 $3$ 行，第一行是 $n,k$，第二行是序列 $a$，第三行是序列 $b$。

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

- $1 \le t \le 1000$。 - $1 \le k \le n \le 3000$。 - $\sum n \le 3000$。 - $\forall i \in ([1,n] \cap \mathbb N ), -10^9 \le a_i, b_i \le 10^9 $。