CF1749B.Death's Blessing

You are playing a computer game. To pass the current level, you have to kill a big horde of monsters. In this horde, there are $n$ monsters standing in the row, numbered from $1$ to $n$. The $i$-th monster has $a_i$ health and a special "Death's Blessing" spell of strength $b_i$ attached to it.

You are going to kill all of them one by one. It takes exactly $h$ seconds to kill a monster with health $h$.

When the $i$-th monster dies, it casts its spell that increases the health of its neighbors by $b_i$ (the neighbors of the $j$-th monster in the row are the monsters on places $j - 1$ and $j + 1$. The first and the last monsters have only one neighbor each).

After each monster is killed, the row shrinks, so its former neighbors become adjacent to each other (so if one of them dies, the other one is affected by its spell). For example, imagine a situation with $4$ monsters with health $a = [2, 6, 7, 3]$ and spells $b = [3, 6, 0, 5]$. One of the ways to get rid of the monsters is shown below:

$2$

$6$

$7$

$3$

$\xrightarrow{6\ s}$

$8$

$13$

$3$

$\xrightarrow{13\ s}$

$8$

$3$

$\xrightarrow{8\ s}$

$6$

$\xrightarrow{6\ s}$

${}$

$3$

$6$

$0$

$5$

$3$

$0$

$5$

$3$

$5$

$5$

The first row represents the health of each monster, the second one — the power of the spells.

As a result, we can kill all monsters in $6 + 13 + 8 + 6$ $=$ $33$ seconds. Note that it's only an example and may not be the fastest way to get rid of the monsters.

What is the minimum time required to kill all monsters in the row?

你正在玩一款电脑游戏。为了通过当前关卡，你需要消灭一大群怪物。这群怪物共有 $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\ s}$

$8$

$13$

$3$

$\xrightarrow{13\ s}$

$8$

$3$

$\xrightarrow{8\ s}$

$6$

$\xrightarrow{6\ s}$

${}$

$3$

$6$

$0$

$5$

$3$

$0$

$5$

$3$

$5$

$5$

第一行表示每只怪物的生命值，第二行表示对应法术的强度。

最终，我们可在 $6 + 13 + 8 + 6 = 33$ 秒内消灭全部怪物。注意这仅是一个示例，未必是消灭所有怪物的最快方式。

问：消灭整列怪物所需的最短时间是多少？

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of monsters in the row.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the initial health of corresponding monsters.

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 10^9$), where $b_i$ is the strength of the spell for the $i$-th monster.

It's guaranteed that the sum of $n$ doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print one integer — the minimum possible total time to kill all monsters.

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

In the first test case, there is only one monster that will be killed in $10$ seconds.

In the second test case, it's optimal to kill the first monster, the last monster and then the middle one. It will take $100 + 100 + (1 + 1 + 1)$ $=$ $203$ seconds.

In the third test case, it's optimal to kill the first monster, then the third one, then the fourth one and finally the second one. It will take $2 + 7 + (3 + 0) + (3 + 6 + 5)$ $=$ $26$ seconds.

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

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

在第三个测试用例中，最优策略是先消灭第一个怪物，然后消灭第三个怪物，接着消灭第四个怪物，最后消灭第二个怪物。总共耗时 $2 + 7 + (3 + 0) + (3 + 6 + 5)$ $=$ $26$ 秒。