解题思路

先把题目中双方对 $A-B$ 的影响拆开来看。

设某个位置 $i$ 的权值为：

题目内容

给定两个长度均为 $n$ 的整数数组 $a$={$a_1,a_2,…,a_n$} 与$b$={$b_1,b_2,…,b_n$}，进行一场回合制对抗游戏，规则如下：

• 共有 $n$个位置$1$∼$n$，每个位置只能被选择一次，由 Alice 先手，两人轮流行动；
• 轮到 Alice 行动时：选择一个未被选择的位置 $i$，获得收益 $a_i$ 并支付代价 $b_i$，本回合净收益为 $(a_i−b_i)$；
• 轮到 Bob 行动时：选择一个未被选择的位置$i$，获得收益 $b_i$ 并支付代价 $a_i$，本回合净收益为 $(b_i−a_i)$；
• 所有位置被选择后游戏结束，设 $Alice$ 的总净收益为$A$，$Bob$ 的总净收益为$B$；
• 两人均采取最优策略：$Alice$ 希望最大化 $A−B$，$Bob$ 希望最小化 $A−B$，双方完全理性，总是选择对自己最有利的行动。

请输出在最优博弈下的分差$A−B$。

输入描述

每个测试文件包含多组测试数据： 第一行输入一个整数$T (1≤T≤10^5)$，表示测试数据组数；

每组测试数据：

• 第一行输入一个整数 $n (1≤n≤2×10^5)$，表示数组长度；

• 第二行输入$n$个整数$a_1,a_2,…,a_n (∣a_i∣≤10^9)$；

• 第三行输入$n$ 个整数$b_1,b_2,…,b_n (∣b_i∣≤10^9)$；

  保证所有测试数据中$n$ 的总和不超过 $3×10^5$。

输出描述

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

样例1

输入

3
3
3 1 2
2 2 2
2
1 10
10 1
4 
5 1 1 1 
1 4 4 4

输出

0
0
-5