CF2173B Niko's Tactical Cards

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

在第一个测试用例中，一种最优策略如下： | 回合 | 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 | 由 ChatGPT 5 翻译