E. Максимальная моногонность
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$ и массив $$$b$$$ длины $$$n$$$. Назовем стоимостью отрезка $$$[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$$$.

Найдите максимально возможную суммарную стоимость попарно непересекающихся отрезков $$$[l_j, r_j]$$$, $$$1 \le l_j \le r_j \le n$$$, суммарная длина которых равна $$$k$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ $$$(1 \le t \le 1000)$$$ — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 3000$$$) — длину массива $$$a$$$ и суммарную длину отрезков.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — элементы массива $$$b$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$3000$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — максимально возможную суммарную стоимость таких отрезков.

Пример
Входные данные
5
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
7 2
1 3 7 6 4 7 2
1 5 3 2 7 4 5
4 2
17 3 5 8
16 2 5 9
Выходные данные
0
10
0
16
28
Примечание

В первом наборе входных данных стоимость любого отрезка равна $$$0$$$, поэтому суммарная стоимость равна $$$0$$$.

Во втором наборе входных данных можно взять отрезок $$$[1, 1]$$$ со стоимостью $$$8$$$ и отрезок $$$[3, 3]$$$ со стоимостью $$$2$$$, чтобы получить сумму $$$10$$$. Можно показать, что это оптимальное решение.

В третьем наборе входных данных нас интересуют только отрезки длины $$$1$$$, а стоимость любого такого отрезка равна $$$0$$$.

В четвертом наборе входных данных можно показать, что оптимальная сумма равна $$$16$$$. Например, можно взять отрезки $$$[3, 3]$$$ и $$$[4, 4]$$$.