A16537 | $Niko's Tactical Cards$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

输入 #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

C++ 编辑器

输入

输出