CF1038C.Gambling

Two players A and B have a list of $n$ integers each. They both want to maximize the subtraction between their score and their opponent's score.

In one turn, a player can either add to his score any element from his list (assuming his list is not empty), the element is removed from the list afterward. Or remove an element from his opponent's list (assuming his opponent's list is not empty).

Note, that in case there are equal elements in the list only one of them will be affected in the operations above. For example, if there are elements ${1, 2, 2, 3}$ in a list and you decided to choose $2$ for the next turn, only a single instance of $2$ will be deleted (and added to the score, if necessary).

The player A starts the game and the game stops when both lists are empty. Find the difference between A's score and B's score at the end of the game, if both of the players are playing optimally.

Optimal play between two players means that both players choose the best possible strategy to achieve the best possible outcome for themselves. In this problem, it means that each player, each time makes a move, which maximizes the final difference between his score and his opponent's score, knowing that the opponent is doing the same.

两名玩家 A 和 B 各自拥有一组包含 $n$ 个整数的列表。双方均希望最大化自己得分与对手得分之间的差值。

在一轮操作中，一名玩家可执行以下两种操作之一（前提是相应列表非空）：

• 将自己列表中的任意一个元素加到自己的得分上（该元素随后将从列表中移除）；
• 从对手的列表中移除任意一个元素。

注意：若列表中存在相等的元素，则上述操作每次仅影响其中一个副本。例如，若某列表为 $\{1, 2, 2, 3\}$，而当前轮次选择 $2$，则仅有一个 $2$ 被删除（若为加至得分的操作，则该 $2$ 同时被加入得分）。

玩家 A 先手，当双方列表均为空时游戏结束。假设双方均以最优策略进行游戏，求游戏结束时 A 的得分与 B 的得分之差。

此处“双方均以最优策略进行游戏”是指：双方始终采用能为自己带来最优结果的最佳策略。本题中即指：每位玩家在每一步操作中，均会选择使最终自身得分与对手得分之差最大化的行动，且其决策基于对手也将采取同样最优策略这一前提。

The first line of input contains an integer $n$ ($1 \le n \le 100\,000$) — the sizes of the list.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^6$), describing the list of the player A, who starts the game.

The third line contains $n$ integers $b_i$ ($1 \le b_i \le 10^6$), describing the list of the player 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 的列表。

Output the difference between A's score and B's score ($A-B$) if both of them are playing optimally.

输出在双方都采取最优策略的情况下，A 的得分与 B 的得分之差（$A-B$）。

In the first example, the game could have gone as follows:

• A removes $5$ from B's list.
• B removes $4$ from A's list.
• A takes his $1$.
• B takes his $1$.

Hence, A's score is $1$, B's score is $1$ and difference is $0$.

There is also another optimal way of playing:

• A removes $5$ from B's list.
• B removes $4$ from A's list.
• A removes $1$ from B's list.
• B removes $1$ from A's list.

The difference in the scores is still $0$.

In the second example, irrespective of the moves the players make, they will end up with the same number of numbers added to their score, so the difference will be $0$.

在第一个例子中，游戏可能按如下方式进行：

• A 从 B 的列表中移除 $5$。
• B 从 A 的列表中移除 $4$。
• A 取走自己的 $1$。
• B 取走自己的 $1$。

因此，A 的得分为 $1$，B 的得分为 $1$，差值为 $0$。

还存在另一种最优的进行方式：

• A 从 B 的列表中移除 $5$。
• B 从 A 的列表中移除 $4$。
• A 从 B 的列表中移除 $1$。
• B 从 A 的列表中移除 $1$。

此时得分差值仍为 $0$。

在第二个例子中，无论双方如何行动，最终各自加入得分的数字个数都相同，因此差值恒为 $0$。