Problem Statement

Little Atom has two sequences, $a$ and $b$, each of length $n$. The "value" of an interval $[l, r]$ $(1 \leq l \leq r \leq n)$ is defined as $|b_r - a_l|$.

Two intervals $[l_1, r_1]$ $(1 \leq l_1 \leq r_1 \leq n)$ and $[l_2, r_2]$ $(1 \leq l_2 \leq r_2 \leq n)$ are non-overlapping if $r_1 < l_2$ or $r_2 < l_1$.

The length of an interval $[l, r]$ $(1 \leq l \leq r \leq n)$ is defined as $r - l + 1$.

Given sequences $a$ and $b$, Little Atom wants to find several non-overlapping intervals, with a total length of $k$, such that the sum of their values is maximized.

Input Format

The first line contains the total number of test cases $t$.

For each test case, there are 3 lines:

• The first line contains two integers $n$ and $k$.
• The second line contains the sequence $a$.
• The third line contains the sequence $b$.

Output Format

For each test case, output the maximum possible sum of the values as described.

Sample Input #1

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

Sample Output #1

0
5
0

Hints

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

There is an $O(n^2)$ solution, and you may want to challenge yourself if time permits qwq.