您正在玩电脑游戏。要通过当前的关卡,你必须杀死一大群怪物。在这个部落中,有$$$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$$$ 秒内杀死所有怪物。请注意,这只是一个示例,可能不是摆脱怪物的最快方法。
杀死该行中的所有怪物所需的最短时间是多少?
输入
第一行包含一个整数 $$$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$$$ 秒。