UESTC is moving to the beautiful new campus which locates in the suburb of Chengdu. WCM is taking charge of arranging
 the buses for the students who are about to move to the new campus. There are two large transportation companies (which
 we¡¯ll call A and B) in Chengdu. However, the two transportation companies are very busy, so on any given day they are 
only able to send limited number of buses.

Here¡¯s the problem WCM faces. He gets a list of how many buses are available from each company over each of the next
 n days. But he can only contact one of the companies in any given day. On day i, there are ai(ai>0) buses available if he 
contacts Company A and there are bi(bi>0) buses available if he contacts Company B. He also has the ability to change
 from one company to the other, but doing this takes one day in which no buses are available.

So, given a sequence of n days, a plan is specified by a choice of A, B, or ¡°change¡± for each day, with the constraint that 
choice A and B cannot appear in consecutive days. For example, if he contacts Company A in day i, and he wants to switch
 to company B, then his choice for day i+1 must be ¡°change¡±, and then his choice for day i+2 can be B. The value of a plan 
is the total number of buses that he manages to arrange for the students of UESTC over the n days: so it¡¯s the sum of ai 
over all days in which the buses are available from Company A, plus the sum of bi over all days in which the buses are 
available from Company B.

The problem: 

Given the values of a1, a2, a3¡­ an and b1, b2, b3¡­ bn, find a plan of the maximum value(Such a plan is called optimal).
 Note that your plan can start with either of the company A or B in day 1.

Example:
 Suppose n=4 and the values of ai and bi are given by the following table.



Then the plan of the maximum value would be to choose A for day 1, then ¡°change¡± for day 2, and then B for day 3 and 4.
 The value of this plan would be 11+0+21+23=55.

Facing this problem, WCM feels despaired. He asks you for help to solve this problem. Give an efficient algorithm that takes
 values for a1, a2¡­ an and b1, b2¡­ bn and returns the value of an optimal plan.

Input

The input contains an integer one the first line, which indicates the number of test cases. Each test case consists of three lines.
 The first line contains one positive integer n,( 0 < n <= 1000000 ),which means the number of the days. The second line contains
 n positive integer, a1,a2,¡­,an,( 0 < ai <= 100 ), ai means the number of buses which can be available if WCM contacts
 Company A in the i-th day; The third line contains n positive integer, b1,b2,¡­,bn,( 0 < bi <= 100 ), bi means the number of 
buses which can be available if WCM contacts Company B in the i-th day.


Output

For each test case, output one number on a line which represents the value of the optimal plan, i.e. the maximum of the 
number of the available buses over the n days.

Sample input

2
4
11 2 2 9
4 1 21 23
3
1 3 1
7 7 7

Sample output

55
21

Source

UESTC 5th programming contest