题目描述

你正在玩一款电脑游戏。为了通过当前关卡，你需要消灭一大群怪物。在这群怪物中，有 $n$ 个怪物排成一排，编号从 $1$ 到 $n$。第 $i$ 个怪物有 $a_i$ 点生命值，并且附带一个强度为 $b_i$ 的特殊“死亡祝福”法术。

你需要依次消灭所有怪物。消灭一个生命值为 $h$ 的怪物需要恰好 $h$ 秒。

当第 $i$ 个怪物死亡时，它会释放法术，使其相邻怪物的生命值各增加 $b_i$（第 $j$ 个怪物的相邻怪物是第 $j-1$ 个和第 $j+1$ 个怪物。第一个和最后一个怪物各只有一个相邻怪物）。

每当一个怪物被消灭后，队列会收缩，因此它原来的相邻怪物会变为彼此相邻（如果其中一个死亡，另一个也会受到其法术影响）。例如，假设有 $4$ 个怪物，其生命值为 $a = [2, 6, 7, 3]$，法术强度为 $b = [3, 6, 0, 5]$。消灭怪物的一种方式如下所示：

$2$ $6$ $7$ $3$ $\xrightarrow{6\ \text{s}}$ $8$ $13$ $3$ $\xrightarrow{13\ \text{s}}$ $8$ $3$ $\xrightarrow{8\ \text{s}}$ $6$ $\xrightarrow{6\ \text{s}}$ $\{\}$

$3$ $6$ $0$ $5$ $3$ $0$ $5$ $3$ $5$ $5$

第一行表示每个怪物的生命值，第二行表示法术的强度。最终，我们可以在 $6 + 13 + 8 + 6 = 33$ 秒内消灭所有怪物。注意，这只是一个例子，并不一定是消灭怪物所需的最短时间。

请你计算消灭所有怪物所需的最短时间。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示怪物的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示每个怪物的初始生命值。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \le b_i \le 10^9$），其中 $b_i$ 表示第 $i$ 个怪物的法术强度。

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

输出格式

对于每个测试用例，输出一个整数，表示消灭所有怪物所需的最短总时间。

说明/提示

在第一个测试用例中，只有一个怪物，将在 $10$ 秒内被消灭。

在第二个测试用例中，最优方案是先消灭第一个怪物，再消灭最后一个怪物，最后消灭中间的怪物。总共需要 $100 + 100 + (1 + 1 + 1) = 203$ 秒。

在第三个测试用例中，最优方案是先消灭第一个怪物，然后是第三个，再是第四个，最后是第二个。总共需要 $2 + 7 + (3 + 0) + (3 + 6 + 5) = 26$ 秒。

由 ChatGPT 4.1 翻译

样例

4
1
10
0
3
100 1 100
1 100 1
4
2 6 7 3
3 6 0 5
2
1000000000 1000000000
1000000000 1000000000

10
203
26
3000000000