CF1859E Maximum Monogonosity

You are given an array $ a $ of length $ n $ and an array $ b $ of length $ n $ . The cost of a segment $ [l, r] $ , $ 1 \le l \le r \le n $ , is defined as $ |b_l - a_r| + |b_r - a_l| $ . Recall that two segments $ [l_1, r_1] $ , $ 1 \le l_1 \le r_1 \le n $ , and $ [l_2, r_2] $ , $ 1 \le l_2 \le r_2 \le n $ , are non-intersecting if one of the following conditions is satisfied: $ r_1 < l_2 $ or $ r_2 < l_1 $ . The length of a segment $ [l, r] $ , $ 1 \le l \le r \le n $ , is defined as $ r - l + 1 $ . Find the maximum possible sum of costs of non-intersecting segments $ [l_j, r_j] $ , $ 1 \le l_j \le r_j \le n $ , whose total length is equal to $ k $ .

Each test consists of multiple test cases. The first line contains a single integer $ t $ $ (1 \le t \le 1000) $ — the number of sets of input data. The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 3000 $ ) — the length of array $ a $ and the total length of segments. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^9 \le a_i \le 10^9 $ ) — the elements of array $ a $ . The third line of each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ -10^9 \le b_i \le 10^9 $ ) — the elements of array $ b $ . It is guaranteed that the sum of $ n $ over all test case does not exceed $ 3000 $ .

For each test case, output a single number — the maximum possible sum of costs of such segments.

In the first test case, the cost of any segment is $ 0 $ , so the total cost is $ 0 $ . In the second test case, we can take the segment $ [1, 1] $ with a cost of $ 8 $ and the segment $ [3, 3] $ with a cost of $ 2 $ to get a total sum of $ 10 $ . It can be shown that this is the optimal solution. In the third test case, we are only interested in segments of length $ 1 $ , and the cost of any such segment is $ 0 $ . In the fourth test case, it can be shown that the optimal sum is $ 16 $ . For example, we can take the segments $ [3, 3] $ and $ [4, 4] $ .