← 返回题目列表

Codeforces · 2173/B

B. 尼科的战术卡

中文机器翻译题面 查看原题

Niko 正在玩游戏。她的分数由整数 $$$k$$$ 表示,最初为 $$$0$$$。

游戏有 $$$n$$$ 回合。在第 $$$i$$$ 回合,Niko 得到一张上面有整数 $$$a_i$$$ 的红牌,以及上面有整数 $$$b_i$$$ 的蓝牌。她必须准确选择 一 卡片并根据她的选择更新她的分数:

  • 如果她选择红牌,她的分数变为 $$$k - a_i$$$,其中 $$$k$$$ 是她在回合前的分数。
  • 如果她选择蓝牌,她的分数变为 $$$b_i - k$$$,其中 $$$k$$$ 是她在回合前的分数。

此后,游戏进入下一个回合,如果是第 $$$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 在游戏结束时可以获得的最大可能分数。

示例

输入
复制

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

输出
复制

6
12
27

注意

在第一个测试用例中,一个最佳策略如下:

转0123
已选择卡片—蓝色红色红色
分数$$$0$$$$$$-3 - 0 = -3$$$$$$-3 - (-8) = 5$$$$$$5 - (-1) = 6$$$
在第二个测试用例中,一种最佳策略如下:
转012345
已选择卡片—蓝色蓝色蓝色蓝色红色
分数$$$0$$$$$$-5$$$$$$8$$$$$$-9$$$$$$13$$$$$$12$$$