CFCF2173B.Niko's Tactical Cards

普及-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

Niko 正在玩一个游戏。她的分数用一个整数 $k$ 表示，初始值为 $0$ 。

游戏有 $n$ 回合。在第 $i$ 回合，Niko 会获得一张红牌，上面写着整数 $a_i$ ，以及一张蓝牌，上面写着整数 $b_i$ 。她必须从中选择恰好一张，并根据选择更新她的分数：

随后游戏进入下一回合，或者如果已进行到第 $n$ 回合则游戏结束。

你的任务是求出 Niko 最终可能获得的最大分数。

每个测试用例包含多组数据。第一行包含测试用例个数 $t$ （ $1 \le t \le 10^3$ ）。接下来是每个测试用例的描述。

每个测试用例第一行包含一个整数 $n$ （ $1 \le n \le 10^5$ ），表示回合数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $-10^9 \le a_i \le 10^9$ ）。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ （ $-10^9 \le b_i \le 10^9$ ）。

保证所有测试用例中 $n$ 的总和不超过 $10^5$ 。

对于每个测试用例，输出一个整数，表示 Niko 可能获得的最大分数。

输入#1

3
3
4 -8 -1
-3 -7 0
5
-3 1 0 7 1
-5 3 -1 4 -5
5
-7 7 5 4 9
-9 -3 3 2 2

输出#1

6
12
27

在第一个测试用例中，一种最优策略如下：

回合	0	1	2	3
选牌	—	蓝牌	红牌	红牌
分数	0	$-3 - 0 = -3$	$-3 - (-8) = 5$	$5 - (-1) = 6$

在第二个测试用例中，一种最优策略如下：

回合	0	1	2	3	4	5
选牌	—	蓝牌	蓝牌	蓝牌	蓝牌	红牌
分数	0	$-5$	8	$-9$	13	12