November 14 is Tartar Sauce Day in Japan. At a fried oyster festival, someone asked Aki for a little more sauce. Aki took the request seriously and ran pipes between the stalls.
There are $$$n$$$ stalls numbered from $$$1$$$ to $$$n$$$ in clockwise order. For $$$1 \le i \lt n$$$, pipe $$$i$$$ connects stalls $$$i$$$ and $$$i+1$$$. Pipe $$$n$$$ connects stalls $$$n$$$ and $$$1$$$.
Each stall $$$i$$$ has an integer $$$a_i$$$. If $$$a_i \gt 0$$$, the stall receives $$$a_i$$$ liters of sauce per second from outside the ring. If $$$a_i \lt 0$$$, then $$$-a_i$$$ liters of sauce per second are taken from the stall. For example, if $$$a_i = -3$$$, three liters per second are taken from the stall. If $$$a_i = 0$$$, no sauce is supplied or taken away at the stall.
For each pipe, you can choose the flow direction and a constant nonnegative integer flow rate in liters per second for free. The rate may be zero. Pipe $$$i$$$ can carry at most $$$b_i$$$ liters per second in either direction. You can replace pipe $$$i$$$ with one of unlimited capacity for $$$c_i$$$ units of money.
At each stall, the total inflow must equal the total outflow. This includes both the flows through the pipes and any sauce supplied or taken away at the stall. Find the minimum total cost of replacing pipes so that this requirement can be met.
The first line contains an integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of stalls.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$). It is guaranteed that $$$a_1 + a_2 + \cdots + a_n = 0$$$.
The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^9$$$) — the pipe capacities.
The fourth line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — the pipe replacement costs.
Output a single integer — the minimum total cost of replacing pipes.
It can be shown that a valid choice of flows always exists if all pipes are replaced.
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
In the first example, no pipes need to be replaced. Pipe $$$1$$$ can carry two liters per second from stall $$$1$$$ to stall $$$2$$$. Pipe $$$3$$$ can carry one liter per second from stall $$$4$$$ to stall $$$3$$$, and pipe $$$4$$$ can carry two liters per second from stall $$$1$$$ to stall $$$4$$$. There is no flow through pipe $$$2$$$.
In the second example, if any two pipes are left in place, their common stall has no flow through its pipes even though its $$$a_i$$$ is nonzero. You can keep pipe $$$2$$$ and send two liters per second from stall $$$1$$$ to stall $$$2$$$ and one liter per second from stall $$$1$$$ to stall $$$3$$$. This costs $$$2 + 4 = 6$$$.
In the third example, four liters per second must be sent from stall $$$3$$$ to stall $$$5$$$. The clockwise route requires replacing pipes $$$3$$$ and $$$4$$$ at a cost of $$$15$$$. The counterclockwise route requires replacing pipes $$$2$$$, $$$1$$$, and $$$5$$$ at a cost of $$$6$$$. The second route costs less.
In the fourth example, the flow rate in every pipe can be set to zero.
In the fifth example, stall $$$3$$$ must receive two liters per second from stall $$$1$$$. With the original pipes, the route through stall $$$2$$$ can carry at most one liter per second, and the route through stall $$$4$$$ cannot carry any sauce. Replacing just one pipe on a route does not increase its capacity. Replacing both pipes on either of these routes costs $$$9$$$ and lets the route carry the required amount.
In the sixth example, any two pipes with zero flow cut off a nonempty part of the ring whose sum of $$$a_i$$$ is nonzero. Therefore, at most one pipe can be kept. For example, if you keep pipe $$$4$$$, you can send $$$10^9$$$ and $$$10^9-1$$$ liters per second clockwise through pipes $$$1$$$ and $$$2$$$, respectively, and one liter per second counterclockwise through pipe $$$3$$$.
| Name |
|---|


