RESTAURANTS

As the network manager of a restaurant chain, you must choose where to open stores along the new national road. $N$ candidate positions have been preselected, and stores can be opened at any of these. For each candidate position $1\le i\le N$, the expected profit from opening a store there has been calculated based on whether stores will open at neighboring positions. If no store opens at positions $i-1$ and $i+1$, the expected profit from the store at position $i$ is $a_i$. If a store opens at one of positions $i-1$ or $i+1$, the expected profit is $b_i$. If stores open at both positions $i-1$ and $i+1$, the expected profit is $c_i$ ($c_1$ and $c_N$ are not defined, and for each position $i$, it holds that $a_i\ge b_i\ge c_i\ge 0$).

Write a program that selects the positions where stores should be opened to maximize profit.

Input

The first line of input contains the number of candidate positions $N$. The second line contains $N$ numbers, the values of $a_1$, $...$, $a_N$. The third line contains $N$ numbers, the values of $b_1$, $...$, $b_N$. Finally, the fourth line contains $N-2$ numbers, the values of $c_2$, $...$, $c_{N-1}$.

Output

The output must consist of one line containing exactly one integer, the maximum profit that can be obtained

Constraints

$2\le N\le 1.000.000$
$0\le c_i\le b_i\le a_i\le 1.000$
Maximum Execution Time: 2 sec
Available Memory: 64 MB

Example of Input - Output

STDIN (restaurants.in)

8
10 9 15 8 18 12 6 8
6 5 8 7 16 10 5 7
3 6 6 12 9 4

STDOUT (restaurants.out)

61

Explanation of the Example

The optimal solution is to open restaurants at positions $1$, $3$, $5$, $6$, $7$, and $8$. Thus, the expected profit is $61$ $(10+0+15+0+16+9+4+7)$.