Longest Simple Cycle
Contest: Educational Codeforces Round 103 (Rated for Div. 2)
Difficulty rating: 1600
Tags: dp, graphs, greedy

You have $$$n$$$ chains, the $$$i$$$-th chain consists of $$$c_i$$$ vertices. Vertices in each chain are numbered independently from $$$1$$$ to $$$c_i$$$ along the chain. In other words, the $$$i$$$-th chain is the undirected graph with $$$c_i$$$ vertices and $$$(c_i - 1)$$$ edges connecting the $$$j$$$-th and the $$$(j + 1)$$$-th vertices for each $$$1 \le j < c_i$$$.

Now you decided to unite chains in one graph in the following way:

1. the first chain is skipped;
2. the $$$1$$$-st vertex of the $$$i$$$-th chain is connected by an edge with the $$$a_i$$$-th vertex of the $$$(i - 1)$$$-th chain;
3. the last ($$$c_i$$$-th) vertex of the $$$i$$$-th chain is connected by an edge with the $$$b_i$$$-th vertex of the $$$(i - 1)$$$-th chain.

Picture of the first test case. Dotted lines are the edges added during uniting process

Calculate the length of the longest simple cycle in the resulting graph.

A simple cycle is a chain where the first and last vertices are connected as well. If you travel along the simple cycle, each vertex of this cycle will be visited exactly once.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains the single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of chains you have.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$2 \le c_i \le 10^9$$$) — the number of vertices in the corresponding chains.

The third line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_1 = -1$$$; $$$1 \le a_i \le c_{i - 1}$$$).

The fourth line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$b_1 = -1$$$; $$$1 \le b_i \le c_{i - 1}$$$).

Both $$$a_1$$$ and $$$b_1$$$ are equal to $$$-1$$$, they aren't used in graph building and given just for index consistency. It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output format:
For each test case, print the length of the longest simple cycle.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the longest simple cycle is shown below:

We can't increase it with the first chain, since in such case it won't be simple — the vertex $$$2$$$ on the second chain will break simplicity.

Example input:
3
4
3 4 3 3
-1 1 2 2
-1 2 2 3
2
5 6
-1 5
-1 1
3
3 5 2
-1 1 1
-1 3 5

Example output:
7
11
8

Editorial:
Suppose, we've built the graph and chosen any simple cycle. Due to the nature of the graph, any simple cycle right part is part of one of the chains. So, let's for each chain calculate the longest simple path with its right part on this chain and denote it as $$$len_i$$$.
Obviously, $$$len_1 = 0$$$. Now, let's look at chain $$$i$$$. If we go along the cycle in both ways, we will step to vertices $$$a_i$$$ and $$$b_i$$$ of the previous chain. If $$$a_i = b_i$$$ then we closed cycle and it's the only possible cycle, so $$$len_i = c_i + 1$$$.
Otherwise, we can either go from $$$a_i$$$ and $$$b_i$$$ and meet each other closing the cycle with part of the $$$(i - 1)$$$-th chain between $$$a_i$$$-th and $$$b_i$$$-th vertices — this part has $$$|a_i - b_i|$$$ edges and our cycle will have length $$$c_i + 1 + |a_i - b_i|$$$.
But if we decide to go in different ways, then we will meet the first and the last vertices of the $$$(i - 1)$$$-th chain. After that, we'll go to the $$$a_{i - 1}$$$-th and the $$$b_{i - 1}$$$-th vertices of $$$(i - 2)$$$-th chain and will make almost the same choice.
But, instead of recurrently solving the same problem, we can note that, in fact, we took a cycle that ends at the $$$(i - 1)$$$-th chain, erased the part between vertices $$$a_i$$$ and $$$b_i$$$, and merged it with our $$$i$$$-th chain part, so the length of this merged cycle will be equal to $$$c_i + 1 + len_{i - 1} - |a_i - b_i|$$$. Since we maximize $$$len_i$$$ we just choose, what part: $$$|a_i - b_i|$$$ or $$$len_{i - 1} - |a_i - b_i|$$$ is longer and take it.
As a result, we can iterate from left to right, calculate all $$$len_i$$$ and print the maximum among them.