E2. Игра с шариками (сложная версия)
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Простая и сложная версии этой задачи отличаются друг от друга только ограничениями на количество наборов входных данных и $$$n$$$. В сложной версии количество наборов входных данных не превосходит $$$10^4$$$, а сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Кроме того, никаких дополнительных ограничений на значение $$$n$$$ в одиночном наборе входных данных нет.

Недавно Алисе и Бобу родители подарили шарики $$$n$$$ различных цветов: получилось, что у Алисы $$$a_1$$$ шариков цвета $$$1$$$, $$$a_2$$$ шариков цвета $$$2$$$,..., $$$a_n$$$ шариков цвета $$$n$$$. У Боба: $$$b_1$$$ шариков цвета $$$1$$$, $$$b_2$$$ шариков цвета $$$2$$$, ..., $$$b_n$$$ шариков цвета $$$n$$$. Все $$$a_i$$$ и $$$b_i$$$ от $$$1$$$ до $$$10^9$$$.

Посовещавшись, Алиса и Боб придумали следующую игру: игроки ходят по очереди, начиная с Алисы. На своём ходу игрок выбирает такой цвет $$$i$$$, что у обоих игроков есть хотя бы по одному шарику этого цвета. Он выбрасывает один шарик цвета $$$i$$$, а его противник — все шарики цвета $$$i$$$. Игра заканчивается, когда не существует такого цвета $$$i$$$, что у обоих игроков есть хотя бы по одному шарику этого цвета.

Счёт в игре — это количество оставшихся шариков у Алисы минус количество оставшихся шариков у Боба по окончании игры. То есть счёт равен $$$(A-B)$$$, где $$$A$$$ — количество шариков у Алисы, а $$$B$$$ — количество шариков у Боба в конце игры. Алиса хочет максимизировать счёт, а Боб — минимизировать.

Посчитайте, какой счёт будет в конце игры, если оба игрока играют оптимально.

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

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

Каждый набор входных данных состоит из трех строк:

  • в первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество цветов шариков;
  • во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — количество шариков $$$i$$$-го цвета у Алисы;
  • в третьей строке заданы $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$), где $$$b_i$$$ — количество шариков $$$i$$$-го цвета у Боба.

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
5
3
4 2 1
1 2 4
4
1 20 1 20
100 15 10 20
5
1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1
3
5 6 5
2 1 7
6
3 2 4 2 5 5
9 4 7 9 2 5
Выходные данные
1
-9
2999999997
8
-6
Примечание

В первом примере один из способов получить счёт $$$1$$$ — следующий:

  1. Алиса выбирает цвет $$$1$$$, выбрасывает $$$1$$$ шарик. Боб также выбрасывает $$$1$$$ шарик;
  2. Боб выбирает цвет $$$3$$$, выбрасывает $$$1$$$ шарик. Алиса также выбрасывает $$$1$$$ шарик;
  3. Алиса выбирает цвет $$$2$$$, выбрасывает $$$1$$$ шарик, а Боб — $$$2$$$ шарика.

В результате у Алисы остается $$$a = [3, 1, 0]$$$, а у Боба — $$$b = [0, 0, 3]$$$. Счёт равен $$$3 + 1 - 3 = 1$$$.

Можно показать, что ни Алиса ни Боб не могут получить лучший счёт, если оба играют оптимально.

Во втором примере Алиса может сначала выбрать цвет $$$1$$$, далее Боб выберет цвет $$$4$$$, после этого Алиса выберет цвет $$$2$$$, и Боб — цвет $$$3$$$. Можно показать, что это оптимальная игра.