T525555 视野一隅

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。

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

$1\le t,\sum n,\sum k\le 400,|a_i|,|b_i|\le 10^8$ 有$n^2$做法，有时间可以挑战一下qwq