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

У каждого из игроков A и B есть по списку, по $$$n$$$ целых чисел в каждом. Они оба хотят максимизировать разность между своими очками и очками соперника.

За один ход, игрок может либо добавить к своим очкам любой элемент из своего списка (если его список не пуст), затем этот элемент удаляется из списка. Или удалить элемента из списка его оппонента (если список его оппонента не пуст).

В случае если в списке есть несколько одинаковых элементов, только один из них будет задействован в какой-то операции. Например, если список состоит из элементов $$$\{1, 2, 2, 3\}$$$ и вы решили выбрать $$$2$$$ для следующего хода, только один экземпляр $$$2$$$ будет удалён (и добавлен к очкам, если это требуется).

Игру начинает игрок А и игра заканчивается когда оба списка становятся пустыми. Найдите разницу между очками A и B, если оба игрока играют оптимально.

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

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

В первой строке входного файла записано целое число $$$n$$$ ($$$1 \le n \le 100\,000$$$) — размер списков.

Вторая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^6$$$), описывающих список игрока A, который ходит первым.

Вторая строка содержит $$$n$$$ целых чисел $$$b_i$$$ ($$$1 \le b_i \le 10^6$$$), описывающих список игрока B.

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

Найдите разницу между очками A и B ($$$A-B$$$), если оба игрока играют оптимально.

Примеры
Входные данные
2
1 4
5 1
Выходные данные
0
Входные данные
3
100 100 100
100 100 100
Выходные данные
0
Входные данные
2
2 1
5 6
Выходные данные
-3
Примечание

В первом примере, игра может выглядеть так:

  • A удаляет $$$5$$$ из списка B.
  • B удаляет $$$4$$$ из списка A.
  • A прибавляет к своим очкам $$$1$$$, и удаляет ее из списка.
  • B прибавляет к своим очкам $$$1$$$, и удаляет ее из списка..

Таким образом, очки A равны $$$1$$$, очки B равны $$$1$$$ и разница $$$0$$$.

Есть также другие варианты оптимальной игры, например:

  • A удаляет $$$5$$$ из списка B.
  • B удаляет $$$4$$$ из списка A.
  • A удаляет $$$1$$$ из списка B.
  • B удаляет $$$1$$$ из списка A.

Разница между очками также $$$0$$$.

Во втором примере, вне зависимости от ходов, в итоге каждый участник добавит к своим очкам одинаковое количество чисел, а значит очки у обоих игроков будут одинаковыми, поэтому разница $$$0$$$.