D. Абсолютная красота
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кирилла есть два массива целых чисел $$$a_1,a_2,\ldots,a_n$$$ и $$$b_1,b_2,\ldots,b_n$$$ длины $$$n$$$. Абсолютная красота массива $$$b$$$ определяется как $$$$$$\sum_{i=1}^{n} |a_i - b_i|.$$$$$$ Здесь $$$|x|$$$ обозначает модуль числа $$$x$$$.

Кирилл может выполнить следующую операцию не более одного раза:

  • выбрать два индекса $$$i$$$ и $$$j$$$ ($$$1 \leq i < j \leq n$$$) и поменять местами значения $$$b_i$$$ и $$$b_j$$$.

Помогите ему найти максимальную возможную красоту массива $$$b$$$ после не более чем одного обмена.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке дано одно число $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — длина массивов $$$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$$$.

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

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

Пример
Входные данные
6
3
1 3 5
3 3 3
2
1 2
1 2
2
1 2
2 1
4
1 2 3 4
5 6 7 8
10
1 8 2 5 3 5 3 1 1 3
2 9 2 4 8 2 3 5 3 1
3
47326 6958 358653
3587 35863 59474
Выходные данные
4
2
2
16
31
419045
Примечание

В первом наборе входных данных любой возможный обмен не изменяет массив $$$b$$$.

Во втором наборе входных данных абсолютная красота массива $$$b$$$ будет равна $$$|1-1| + |2-2| = 0$$$, если не делать единственный возможный обмен. Если же поменять местами первый и второй элементы массива $$$b$$$, абсолютная красота будет равна $$$|1-2| + |2-1| = 2$$$. Таким образом, ответ равен $$$2$$$.

В третьем наборе входных данных Кириллу оптимально не выполнять обмен. Ответ равен $$$2$$$ по аналогии с предыдущим набором входных данных.

В четвёртом наборе входных данных вне зависимости от действий Кирилла абсолютная красота массива $$$b$$$ будет равна $$$16$$$.