G. Treat or Trick
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Julia is going treat or tricking down her street. She can go between any two adjacent houses where an adjacent house is defined as one to its left, right, or across the street. The first time Julia passes by a house, she must go up to the door and knock, and she will either get a trick or a treat. If she gets a trick, it makes her sad, so she loses happiness. If she gets a treat, she will gain some happiness since she got her favorite sour candies. She starts "above" the street on the leftmost end, and she does not need to visit every house before reaching her destination. What is the happiest Julia can be when she reaches the opposite corner (right end and opposite side) of the street?

Input

The first line will contain one integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — the number of houses on each side of the street.

The second line will contain $$$n$$$ integers $$$a_i$$$ ($$$-10^3 \leq a_i \leq 10^3$$$) indicating the amount of happiness gained or lost at each house.

The third line will contain $$$n$$$ integers $$$b_i$$$ ($$$-10^3 \leq b_i \leq 10^3$$$) indicating the amount of happiness gained or lost at each house.

Specifically Julia can move from $$$a_i$$$ to $$$a_{i - 1}$$$, $$$a_{i + 1}$$$, or $$$b_i$$$, or from $$$b_i$$$ to $$$b_{i - 1}$$$, $$$b_{i + 1}$$$, $$$a_i$$$.

Output

Output one integer indicating the maximum happiness Julia can end with. Specifically her path must start at $$$a_1$$$ and end at $$$b_n$$$.

Examples
Input
3
5 2 7
3 -5 4
Output
21
Input
4
5 7 -3 -10
2 -8 -2 5
Output
14
Note

Sample 1 Explanation: We start at $$$a_1$$$ and get 5 happiness.

We go over to $$$b_1$$$ and get 3 more bringing our total to 8.

We can then go back to $$$a_1$$$, and cannot get any more happiness since we've already visited. But, we can go to $$$a_2$$$ from here and get 2 happiness, bringing our total to 10.

Next, we go to $$$a_3$$$ and get 7 more bringing our total to 17.

Finally, we go over to $$$b_3$$$ and get 4 more giving us a final happiness of 21.