19426번 - Maximum Flow 다국어

Bobo has an undirected graph with $(2n + 2)$ vertices conveniently labeled with the following pairs of integers: $(0, 0), (0, 1), \dots, (0, n), (1, 0), (1, 1), \dots, (1, n)$. The graph has three classes of edges.

• The edges of the first class connect vertices $(0, i - 1)$ and $(0, i)$ with capacity $a_i$ for $i \in \{1, 2, \dots, n\}$.
• The edges of the second class connect vertices $(1, i - 1)$ and $(1, i)$ with capacity $b_i$ for $i \in \{1, 2, \dots, n\}$.
• The edges of the third class connect vertices $(0, \lfloor\frac{i - 1}{2} \rfloor)$ and $(1, \lfloor \frac{i}{2}\rfloor)$ with capacity $c_i$ for $i \in \{1, 2, \dots, 2n + 1\}$.

Bobo would like to find the maximum flow from vertex $(0, 0)$ to vertex $(1, n)$.

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

The first line contains an integer $n$ ($1 \leq n \leq 5 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

The third line contains $n$ integers $b_1, b_2, \dots, b_n$.

The fourth line contains $(2n + 1)$ integers $c_1, c_2, \dots, c_{2n + 1}$.

The constraints are: $1 \leq a_i, b_i, c_i \leq 10^9$.

It is guaranteed that the number of test cases does not exceed $10^5$, and the sum of all $n$ does not exceed $5 \cdot 10^5$.

For each test case, output an integer which denotes the maximum flow.