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

14 ноября в Японии отмечается День соуса тартар. На фестивале жареных устриц у Аки попросили ещё немного соуса. Аки восприняла просьбу всерьёз и проложила между прилавками трубы.

Всего есть $$$n$$$ прилавков, пронумерованных от $$$1$$$ до $$$n$$$ по часовой стрелке. Для $$$1 \le i \lt n$$$ труба $$$i$$$ соединяет прилавки $$$i$$$ и $$$i+1$$$. Труба $$$n$$$ соединяет прилавки $$$n$$$ и $$$1$$$.

Для прилавка $$$i$$$ задано целое число $$$a_i$$$. Если $$$a_i \gt 0$$$, в прилавок извне поступает $$$a_i$$$ литров соуса в секунду. Если $$$a_i \lt 0$$$, из прилавка забирают $$$-a_i$$$ литров соуса в секунду. Например, при $$$a_i = -3$$$ из прилавка забирают три литра в секунду. Если $$$a_i = 0$$$, внешней подачи и забора нет.

Для каждой трубы можно бесплатно выбрать направление потока и постоянный неотрицательный целый расход в литрах в секунду. Расход может быть нулевым. Пропускная способность трубы $$$i$$$ равна $$$b_i$$$ литрам в секунду в любом из двух направлений. За $$$c_i$$$ денежных единиц трубу $$$i$$$ можно заменить трубой с неограниченной пропускной способностью.

В каждом прилавке суммарный приток соуса должен равняться суммарному оттоку. При этом учитываются как потоки по трубам, так и внешняя подача и забор. Найдите минимальную суммарную стоимость замены труб, при которой можно выполнить это требование.

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

Первая строка содержит целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество прилавков.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$). Гарантируется, что $$$a_1 + a_2 + \cdots + a_n = 0$$$.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$) — пропускные способности труб.

Четвёртая строка содержит $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — стоимости замены труб.

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

Выведите одно целое число — минимальную суммарную стоимость замены труб.

Можно показать, что допустимая настройка потоков всегда существует, если заменить все трубы.

Примеры
Входные данные
4
4 -2 -1 -1
2 0 1 2
7 4 3 5
Выходные данные
0
Входные данные
3
3 -2 -1
0 0 0
2 5 4
Выходные данные
6
Входные данные
5
0 0 4 0 -4
0 0 0 0 0
1 2 7 8 3
Выходные данные
6
Входные данные
3
0 0 0
0 4 0
2 3 5
Выходные данные
0
Входные данные
4
2 0 -2 0
1 1 0 0
4 5 6 3
Выходные данные
9
Входные данные
4
1000000000 -1 -1000000000 1
0 0 0 0
1000000000 1000000000 1000000000 1000000000
Выходные данные
3000000000
Примечание

В первом примере заменять трубы не нужно. По трубе $$$1$$$ можно направить два литра в секунду от прилавка $$$1$$$ к прилавку $$$2$$$. По трубе $$$3$$$ можно направить один литр в секунду от прилавка $$$4$$$ к прилавку $$$3$$$, а по трубе $$$4$$$ — два литра в секунду от прилавка $$$1$$$ к прилавку $$$4$$$. По трубе $$$2$$$ соус не течёт.

Во втором примере, если оставить любые две трубы без замены, у общего для них прилавка не будет потока по трубам, хотя $$$a_i$$$ для него отлично от нуля. Можно оставить трубу $$$2$$$, направив два литра в секунду от прилавка $$$1$$$ к прилавку $$$2$$$ и один литр в секунду от прилавка $$$1$$$ к прилавку $$$3$$$. Это стоит $$$2 + 4 = 6$$$.

В третьем примере нужно доставить четыре литра в секунду от прилавка $$$3$$$ к прилавку $$$5$$$. Для маршрута по часовой стрелке нужно заменить трубы $$$3$$$ и $$$4$$$ за $$$15$$$ денежных единиц. Для маршрута против часовой стрелки нужно заменить трубы $$$2$$$, $$$1$$$ и $$$5$$$ за $$$6$$$ денежных единиц. Второй маршрут обходится дешевле.

В четвёртом примере во всех трубах можно установить нулевой расход.

В пятом примере прилавку $$$3$$$ нужно получать два литра в секунду от прилавка $$$1$$$. По маршруту через прилавок $$$2$$$ без замены труб можно передать не больше одного литра в секунду, а по маршруту через прилавок $$$4$$$ соус без замены труб пройти не может. Замена одной трубы на маршруте не увеличивает его пропускную способность. Замена обеих труб на любом из этих маршрутов стоит $$$9$$$ денежных единиц и позволяет передать нужный объём.

В шестом примере любые две трубы с нулевым расходом отсекают от остальных непустую часть кольца, в которой сумма $$$a_i$$$ отлична от нуля. Поэтому можно оставить не более одной трубы. Например, если оставить трубу $$$4$$$, по трубам $$$1$$$ и $$$2$$$ можно направить по часовой стрелке $$$10^9$$$ и $$$10^9-1$$$ литров в секунду соответственно, а по трубе $$$3$$$ — один литр в секунду против часовой стрелки.