题目内容

古老的竞技场里遗落了 $n$ 件圣物，每件圣物同时蕴含“光魂”与“暗魂”两种力量。两位角斗士——先行者与后行者——将按照如下规则轮流拾取圣物，直至场地清空：

• 先行者先手，选择一个未被拾取的圣物 $i$，获得 $C_i$ 点光魂并失去 $D_i$ 点暗魂，本回合净收益为 $C_i - D_i$；
• 后行者接着选择，获得 $D_i$ 点暗魂并失去 $C_i$ 点光魂，本回合净收益为 $D_i - C_i$；
• 每个圣物只能被拾取一次。

设最终先行者的总净收益为 $X$，后行者的总净收益为 $Y$。先行者希望最大化最终分差 $X - Y$，后行者则希望最小化该分差。双方完全理性且知晓所有圣物的魂力值，都会采取最优策略。

请你计算在双方最优行动下的最终分差 $X - Y$。

数据范围：

• 测试组数 $T$ 不超过 $10^5$；
• 每组数据中圣物数量 $n$ 的总和不超过 $3 \times 10^5$；
• 所有光魂值 $C_i$ 和暗魂值 $D_i$ 的绝对值均不超过 $10^9$。

输入描述

第一行包含一个整数 $T$，表示测试数据的组数。

接下来对于每组测试数据：

• 第一行包含一个整数 $n$，表示圣物的件数；
• 第二行包含 $n$ 个整数 $C_1, C_2, \dots, C_n$，表示每件圣物蕴含的光魂值；
• 第三行包含 $n$ 个整数 $D_1, D_2, \dots, D_n$，表示每件圣物蕴含的暗魂值。

输出描述

对于每组测试数据，输出一行一个整数，表示在双方都采取最优策略时的分差 $X - Y$。

样例1

输入

1
1
5
3

输出

2

说明

只有 1 件圣物。先行者先手拾取该圣物，获得光魂 $C_1 = 5$，失去暗魂 $D_1 = 3$，本回合净收益为 $5 - 3 = 2$。后行者没有可以拾取的圣物，净收益为 0。最终分差 $X - Y = 2 - 0 = 2$。

从数学不变量角度看，分差始终等于所有圣物的 $\sum (C_i - D_i)$，即 $(5 - 3) = 2$。

样例2

输入

1
2
10 2
5 7

输出

0

说明

共有 2 件圣物，属性分别为 $C_1 = 10, D_1 = 5$ 和 $C_2 = 2, D_2 = 7$。

无论双方如何选择，最终分差均为各圣物贡献之和： $X - Y = (C_1 - D_1) + (C_2 - D_2) = (10 - 5) + (2 - 7) = 5 + (-5) = 0$。

例如，若先行者先选 10‑5（净收益 5），后行者选 2‑7（净收益 2-7 = -5），分差为 $5 - (-5) = 10$？注意：后行者拾取圣物 $i$ 时，自身净收益为 $D_i - C_i$，对分差 $X - Y$ 的影响是减去这个净收益，即 $-(D_i - C_i) = C_i - D_i$。因此无论谁选，每件圣物对 $X - Y$ 的贡献都是 $C_i - D_i$，总和为 0。

样例3

输入

1
3
1 -1 3
2 -3 -2

输出

6

说明

有 3 件圣物，$C = [1, -1, 3]$，$D = [2, -3, -2]$。

分别计算每件圣物的差值贡献：

• 圣物 1：$C_1 - D_1 = 1 - 2 = -1$
• 圣物 2：$C_2 - D_2 = (-1) - (-3) = 2$
• 圣物 3：$C_3 - D_3 = 3 - (-2) = 5$

最终分差 $X - Y = (-1) + 2 + 5 = 6$。无论双方采任何最优次序，该分差恒为 6。