E. L-shaped Dominoes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a $$$2*n$$$ grid, where each cell contains an integer (not necessarily non-negative).

Your task is to find a way to place non-overlapping L-shaped dominoes on this grid, so that the sum of integers on the cells covered by the dominoes is maximum.

An L-shaped domino can be seen as a $$$2*2$$$ domino obtained by removing a $$$1*1$$$ domino.

For example,for the following $$$2*5$$$ grid, the optimal way is shown in the right picture.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$),representing the $$$n$$$ numbers in the first row of this grid.

The third line of contains $$$n$$$ integers $$$b_1,b_2,\ldots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$),representing the $$$n$$$ numbers in the second row of this grid.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer in a new line — the maximum sum you can get.

Example
Input
3
3
-1 -1 -1
-1 -1 -1
5
10 9 10 10 9
10 10 -20 10 9
6
123 -183 100 -213 901 910
281 -182 281 211 129 -999
Output
0
60
2754
Note

Test Case $$$1$$$:

You don't need to place any dominoes.

Test Case $$$2$$$:

The optimal way is shown in the picture above.