There is a giant circular container which is divided into N segments numbered from 0 to N-1.

Each segment has two bottles, one is a bottle of cold drink and other is a bottle of poison. Drinking from bottle of cold drink increases your energy by A[i] while drinking from bottle of poison decreases your energy by B[i].

The corresponding energies for the same are given in input.

Now as it is circular, so bottles in segment N-1 and segment 0 are adjacent. If you do not drink from bottle of cold-drink, then you have to drink from bottle of poison in that segment. Furthermore you cannot drink from bottle of cold-drink in adjacent segments. You have to drink in such a way so that your energy maximizes. Find this maximum value.

Note: Your initial energy will be 0 and the final maximum energy can be negative.

Input

There will be T test cases and in each test case there will be an integer N which is the size of the container.

Next line contain N integers denoting the first array and the second line also contain N integers denoting the second array.

Output

There will be T lines each containing the output for each test case.

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 10000
1 ≤ A[i], B[i] ≤ 10⁹

Sample

Input:
1
3
1 2 3
4 5 6

Output:
-6

Explanation

There are 3 segments and the pairs are (1, 4), (2, 5), (3, 6). The optimal solution is to drink third potion and first two bottle of poison. The answer in this case is (-4 + - 5 + 3 ) = -6.

---

hide comments

	smso: 2019-05-10 15:43:53 dp using 2 arrays with 2 runs: 1st run => drink the first bottle of poison 2nd run => drink the cold-drink
	yash agarwal: 2014-09-29 13:15:14 why my code is giving the compilation error.... my code is running fine in dev c++ and also in ideone.... id :12491895
	Gourav Saha: 2014-09-04 17:13:44 @Rohan you can't take 1 and 3 since the container is circular so first and last segments are adjacent.
	Rohan Phadke: 2014-09-04 16:41:53 wouldn't optimal solution in the given example be drinking poison from only the second bottle and cold-drink from the first and third bottle? 1 + (-5) + 3 = -1
	LeppyR64: 2014-09-03 15:01:37 You must drink from all N sections? It appears so based on the sample input, but the problem doesn't explicitly state it. RE : Yes , you must drink from all the sections . Everything is clearly mentioned in the problem statement. Last edit: 2014-09-03 15:38:16
	nitish rao: 2014-09-01 19:22:34 @Aayush By maximising energy you mean maximising the absolute value of energy, right? RE (Jacob): No, just maximize the energy. Last edit: 2014-09-01 20:44:05