Wookje is a gambler!!

Time limit2sMemory limit256 MB

Summary

Given the starting top faces of N signed coins in two rounds, maximize the difference between the largest reachable first-round sum and the smallest reachable second-round sum using flips of three consecutive coins (clipped at the ends).

Level: Medium7 of 10
Topics: Math, Greedy, Array, Number theory
Solved: No attempts yet

Problem

Wookje is a well known bettor in Las Vegas, and the game he plays most is coin flipping. Each coin used in this game has an integer written on each of its two faces. The two integers have the same absolute value and opposite signs. Different coins may carry different absolute values.

A player goes through two rounds. Both rounds use the same coins, and for each round the dealer shuffles the $N$ coins arbitrarily and lays them out in a row. The face that ends up on top may also differ from round to round. In the first round Wookje must flip coins so that the sum of the numbers facing up is as large as possible, and in the second round he must flip coins so that this sum is as small as possible. (sum of the first round) - (sum of the second round) is the score the player earns.

Wookje uses his thumb, index finger and middle finger, so he always flips three consecutive coins at once. He believes he cannot win unless he flips three consecutive coins, so he never slips and always flips exactly three in a row. The window of three may stick out past either end of the row, so he can also flip only the single coin at an end, or only the two coins at an end. There is no limit on the number of flips.

Wookje is the best bettor, so he always earns the highest score he can. Find the score Wookje earns in this game.

Input

The first line contains the number of coins $N$ . ( $1 \le N \le 10000$ )

The second line contains, in order, the numbers facing up on the $N$ coins laid out in the first round.

The third line contains the same values, in order, for the $N$ coins of the second round.

Every number written on a coin is an integer whose absolute value is at most $10000$ .

Output

Print the score Wookje earns in this game.

Hint

In the first example, flipping -2, -7 and -8 together makes the sum of the first round as large as possible.

For the second round, flipping 1, 8 and -7 and then flipping 7, 5 and 2 makes the sum as small as possible.

Examples4

Example 1
Input
```
6
5 -2 -7 -8 9 1
-9 1 8 -7 5 2
```
Expected output
```
64
```
Example 2
Input
```
1
5
-5
```
Expected output
```
10
```
Example 3
Input
```
1
0
0
```
Expected output
```
0
```
Example 4
Input
```
2
-10000 10000
10000 -10000
```
Expected output
```
40000
```