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$$$) — стоимости замены труб.
Выведите одно целое число — минимальную суммарную стоимость замены труб.
Можно показать, что допустимая настройка потоков всегда существует, если заменить все трубы.
44 -2 -1 -12 0 1 27 4 3 5
0
33 -2 -10 0 02 5 4
6
50 0 4 0 -40 0 0 0 01 2 7 8 3
6
30 0 00 4 02 3 5
0
42 0 -2 01 1 0 04 5 6 3
9
41000000000 -1 -1000000000 10 0 0 01000000000 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$$$ — один литр в секунду против часовой стрелки.