Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

Time Limit: 3.0 Seconds Memory Limit: 65536K

Total Runs: 1107 Accepted Runs: 441

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. ### 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, *a*_{1}, *a*_{2} бн *a*_{n} (0 < *a*_{i} ≤ 100), *a*_{i} 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, *b*_{1}, *b*_{2} бн *b*_{n},(0 < *b*_{i} ≤ 100), *b*_{i} 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

### Sample output

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 *a _{i}*(

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 *a _{i}* over all days in which the buses are available from Company A, plus the sum of

The problem: Given the values of *a _{1}*,

Example: Suppose *n* = 4 and the values of *a _{i}* and

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.Day 1 Day 2 Day 3 Day 4 A 11 2 2 9 B 4 1 21 23

Facing this problem, WCM feels despaired. He asks you for help to solve this problem. Give an efficient algorithm that takes values for *a _{1}*,

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

55 21

Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz