4482: B. Death's Blessing
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：29
通过：13
题目描述
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 ai health and a special "Death's Blessing" spell of strength bi 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 bi (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:
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?
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 bi (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:
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 <= t <= 104) — the number of test cases.
The first line of each test case contains a single integer n (1 <= n <= 2 · 105) — the number of monsters in the row.
The second line contains n integers a1, a2, ..., an (1 <= ai <= 109) — the initial health of corresponding monsters.
The third line contains n integers b1, b2, ..., bn (0 <= bi <= 109), where bi is the strength of the spell for the i-th monster.
It's guaranteed that the sum of n doesn't exceed 2 · 105.
The first line of each test case contains a single integer n (1 <= n <= 2 · 105) — the number of monsters in the row.
The second line contains n integers a1, a2, ..., an (1 <= ai <= 109) — the initial health of corresponding monsters.
The third line contains n integers b1, b2, ..., bn (0 <= bi <= 109), where bi is the strength of the spell for the i-th monster.
It's guaranteed that the sum of n doesn't exceed 2 · 105.
输出格式
For each test case, print one integer — the minimum possible total time to kill all monsters.
输入样例 复制
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
数据范围与提示
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.
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.