Death's Blessing

题意翻译

给定 n 个二元组 $\{(a_i,b_i)\}$。 删除第 $i$ 个元素消耗 $a_i$ 秒，然后让相邻的二元组（注意，第 $1$ 个和第 $n$ 个不相邻）的 $a := a+b_i$，求删除所有元素的最少时间。 给一份~~脚打的~~原题说明部分中 $\LaTeX$ 炸掉的部分： $\Big|^{\ 2}_{\ 3}\ \Big|^{\ 6}_{\ 6}\ \Big|^{\ 7}_{\ 0}\ \Big|^{\ 3}_{\ 5}\ \Big|\ \underrightarrow{6s}\ \Big|^{\ 8}_{\ 3}\ \Big|^{\ 13}_{\ 0}\ \Big|^{\ 3}_{\ 5}\ \Big|\ \underrightarrow{13s}\Big|^{\ 8}_{\ 3}\ \Big|^{\ 3}_{\ 5}\ \Big|\ \underrightarrow{8s}\ \Big|^{\ 6}_{\ 5}\ \Big|\ \underrightarrow{6s}\ \{\}$

题目描述

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?

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

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

输出样例 #1

10
203
26
3000000000

说明

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.

**死亡祝福**

**题意翻译：**
给定n个二元组 \((a_i, b_i)\)。删除第 \(i\) 个元素消耗 \(a_i\) 秒，然后让相邻的二元组（注意，第1个和第 \(n\) 个不相邻）的 \(a := a + b_i\)，求删除所有元素的最少时间。

**题目描述：**
你正在玩一款电脑游戏。为了通过当前关卡，你必须杀死一大群怪物。这群怪物中有 \(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{6s}\) 8 13 3 \(\xrightarrow{13s}\) 8 3 \(\xrightarrow{8s}\) 6 \(\xrightarrow{6s}\) \(\{\} \) 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\)。

**输出格式：**
对于每个测试用例，打印一个整数 —— 杀死所有怪物的最小可能总时间。

**输入输出样例：**

**输入样例 #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
```

**输出样例 #1:**
```
10
203
26
3000000000
```

**说明：**
在第一个测试用例中，只有一个怪物，将在10秒内被杀死。

在第二个测试用例中，最优方法是先杀死第一个怪物，然后是最后一个怪物，最后是中间的一个。这将需要 \(100 + 100 + (1 + 1 + 1) = 203\) 秒。

在第三个测试用例中，最优方法是先杀死第一个怪物，然后是第三个，然后是第四个，最后是第二个。这将需要 \(2 + 7 + (3 + 0) + (3 + 6 + 5) = 26\) 秒。**死亡祝福** **题意翻译：** 给定n个二元组 \((a_i, b_i)\)。删除第 \(i\) 个元素消耗 \(a_i\) 秒，然后让相邻的二元组（注意，第1个和第 \(n\) 个不相邻）的 \(a := a + b_i\)，求删除所有元素的最少时间。 **题目描述：** 你正在玩一款电脑游戏。为了通过当前关卡，你必须杀死一大群怪物。这群怪物中有 \(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{6s}\) 8 13 3 \(\xrightarrow{13s}\) 8 3 \(\xrightarrow{8s}\) 6 \(\xrightarrow{6s}\) \(\{\} \) 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\)。 **输出格式：** 对于每个测试用例，打印一个整数 —— 杀死所有怪物的最小可能总时间。 **输入输出样例：** **输入样例 #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 ``` **输出样例 #1:** ``` 10 203 26 3000000000 ``` **说明：** 在第一个测试用例中，只有一个怪物，将在10秒内被杀死。 在第二个测试用例中，最优方法是先杀死第一个怪物，然后是最后一个怪物，最后是中间的一个。这将需要 \(100 + 100 + (1 + 1 + 1) = 203\) 秒。 在第三个测试用例中，最优方法是先杀死第一个怪物，然后是第三个，然后是第四个，最后是第二个。这将需要 \(2 + 7 + (3 + 0) + (3 + 6 + 5) = 26\) 秒。