C. Шоппинг в поездке
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Али и Бахамин решили провести свои летние каникулы на прекрасных южных побережьях Ирана. Они также согласились немного пошопиться во время поездки — но вместо того, чтобы установить фиксированный бюджет, они решили определить, сколько они потратят, играя в игру.

Игра проходит на двух массивах $$$a$$$ и $$$b$$$, каждый из которых содержит $$$n$$$ целых чисел.

Игра будет длиться $$$k$$$ раундов. На каждом раунде:

  • Сначала Али выбирает два индекса $$$i$$$ и $$$j$$$ ($$$1 \leq i \lt j \leq n$$$);
  • Затем Бахамин переставляет четыре целых числа $$$a_i$$$, $$$a_j$$$, $$$b_i$$$ и $$$b_j$$$ произвольным образом. Обратите внимание, что Бахамин может менять местами числа из разных массивов. Он также может оставить один или оба массива без изменений.

После всех $$$k$$$ раундов значение игры определяется как $$$v=\sum\limits_{i=1}^{n} |a_i-b_i|$$$. Али и Бахамин потратят ровно $$$v$$$ монет во время своей поездки.

Однако их цели совершенно разные:

  • Али хочет потратить как можно меньше, то есть минимизировать $$$v$$$;
  • Бахамин хочет потратить как можно больше, то есть максимизировать $$$v$$$.

Вам нужно найти итоговое количество монет, которое они потратят, если и Али, и Бахамин будут играть оптимально.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq n$$$) — длину массивов $$$a$$$ и $$$b$$$, и количество раундов.

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

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

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — итоговое количество монет, которое они потратят, если и Али, и Бахамин будут играть оптимально.

Пример
Входные данные
5
2 1
1 7
3 5
3 2
1 5 3
6 2 4
5 4
1 16 10 10 16
3 2 2 15 15
4 1
23 1 18 4
19 2 10 3
10 10
4 3 2 100 4 1 2 4 5 5
1 200 4 5 6 1 10 2 3 4
Выходные данные
8
9
30
16
312
Примечание

В первом наборе входных данных Али может выбрать только $$$(i, j) = (1, 2)$$$, и Бахамин может переставить все четыре числа. Таким образом, он может назначить $$$a = [5, 1]$$$ и $$$b = [3, 7]$$$. И значение игры будет $$$v=|5 - 3| + |1 - 7| = 8$$$. Можно показать, что это максимальное возможное значение, которое может достичь Бахамин — другие перестановки, такие как $$$a = [5, 7],\space b = [1, 3]$$$, также возможны, но не имеют большие значения.

Во втором наборе входных данных лучшая стратегия для Бахамина заключается в том, чтобы оставить оба массива без изменений независимо от того, какие индексы выберет Али. Тогда значение игры будет $$$v=|1 - 6| + |5 - 2| + |3 - 4| = 9$$$.