Death's Blessing
Contest: Educational Codeforces Round 138 (Rated for Div. 2)
Difficulty rating: 900
Tags: greedy

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?

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
10
203
26
3000000000

Editorial:
Note that whichever order you choose, the total time will always contain all initial health $$$a_i$$$, in other words, any answer will contain $$$\sum_{i=1}^{n}{a_i}$$$ as its part. So the lower the sum of $$$b_i$$$ you will add to the answer — the better.
Look at some monster $$$i$$$. If you kill it while it has both left and right neighbor, it will add $$$2 \cdot b_i$$$ to the answer. If it is the first or the last in the row, it will add just $$$b_i$$$. And if it is the last monster, it will add $$$0$$$.
There can be only one last monster, so any other will add at least $$$b_i$$$ to the answer. And for any chosen last monster $$$l$$$ you can find the order that gives exactly $$$b_i$$$ for all other monsters. For example, you can firstly kill monsters $$$1, 2, \dots, (l-1)$$$, then $$$n, (n-1), \dots, (l + 1)$$$ and, finally, moster $$$l$$$.
In other words, if the last monster is the $$$l$$$-th one, the total answer will be equal to $$$\sum_{i=1}^{n}{a_i} + \sum_{i=1}^{n}{b_i} - b_l$$$. Since we need to minimize answer, we can choose monster with maximum $$$b_l$$$.
So, the answer is $$$\sum_{i=1}^{n}{a_i} + \sum_{i=1}^{n}{b_i} - \max_{i=1}^{n}{b_i}$$$.