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

В компьютерном классе стоят два ряда компьютеров. В каждом ряду ровно по $$$n$$$ компьютеров и у компьютеров есть своя классификация. Компьютеры в первом ряду имеют классы $$$a_1, a_2, \dots, a_n$$$, а компьютеры во втором ряду — $$$b_1, b_2, \dots, b_n$$$.

Первоначально, все пары соседних компьютеров в каждом ряду соединены кабелем (пары $$$(i, i + 1)$$$ для всех $$$1 \le i < n$$$), а потому ряды образуют две независимые компьютерные сети.

Ваша задача — объединить их в одну общую сеть посредством соединения одной или более пар компьютеров с разных рядов. Соединение $$$i$$$-го компьютера с первого ряда и $$$j$$$-го компьютера второго ряда стоит $$$|a_i - b_j|$$$.

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

Чему равна наименьшая стоимость построить отказоустойчивую сеть?

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

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

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество компьютеров в каждом ряду.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — классы компьютеров в первом ряду.

В третьей строке заданы $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — классы компьютеров во втором ряду.

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

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

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

Пример
Входные данные
2
3
1 10 1
20 4 25
4
1 1 1 1
1000000000 1000000000 1000000000 1000000000
Выходные данные
31
1999999998
Примечание

В первом наборе входных данных, выгодно соединить четыре пары компьютеров:

  1. компьютер $$$1$$$ на первом ряду и компьютер $$$2$$$ на втором ряду: стоимость равна $$$|1 - 4| = 3$$$;
  2. компьютер $$$3$$$ на первом ряду и компьютер $$$2$$$ на втором ряду: стоимость $$$|1 - 4| = 3$$$;
  3. компьютер $$$2$$$ на первом ряду и компьютер $$$1$$$ на втором ряду: стоимость $$$|10 - 20| = 10$$$;
  4. компьютер $$$2$$$ на первом ряду и компьютер $$$3$$$ на втором ряду: стоимость $$$|10 - 25| = 15$$$;
В сумме, $$$3 + 3 + 10 + 15 = 31$$$.

Во втором наборе, выгодно соединить $$$1$$$ на первом ряду и $$$1$$$ на втором ряду, а также $$$4$$$ на первом ряду и $$$4$$$ на втором.