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]$ 的价值总和的最大值。

无

无

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] $ .