题目描述

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 可能获得的最大分数。

说明/提示

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

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

由 ChatGPT 5 翻译

样例

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