B. Подарок смерти
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в компьютерную игру. Для прохождения текущего уровня вам нужно убить полчище монстров. Среди него есть $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно число  — наименьшее возможное суммарное время уничтожения всех монстров.

Пример
Входные данные
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
Примечание

В первом наборе входных данных есть только один монстр, который будет убит за $$$10$$$ секунд.

Во втором наборе, выгодно убить сначала первого монстра, потом последнего, а затем среднего. Уничтожение монстров займет $$$100 + 100 + (1 + 1 + 1)$$$ $$$=$$$ $$$203$$$ секунд.

В третьем наборе, выгодно сначала убить первого монстра, потом третьего, затем четвертого, и, наконец, второго. Уничтожение всех займет $$$2 + 7 + (3 + 0) + (3 + 6 + 5)$$$ $$$=$$$ $$$26$$$ секунд.