Tp学院准备搬到绍兴郊区的新校区去了。Lx负责安排车辆将学生送到新校区去。在绍兴有两家大的客运公司（我们记为A和B）。但是这两家公司业务都很忙，所以他们每天只能提供有限的公交车。

Lx得到了这两家公司在接下来n天里每天所能提供车辆数的清单，但是每天只能由一家公司来工作。假如某一天i，如果由A公司来运送的话，A公司可以提供a_i(a_i>0)辆公交车，如果由B公司来运送的话，B公司可以提供b_i(b_i>0)辆公交车。他有权更换公司，但更换的那一天就没有公交车可用来运送学生。

所以他要制定一个计划在接下来的n天中如何来选择A公司和B公司。但需注意的是你在更换公司的时候不是当天就能更换的。比如第i天是由A公司在运送学生的，但你想接下来的一天换B公司来运送学生，那第i+1天就没有公交车来运送学生，B公司的公交车要第i+2天才能来运送学生。这个计划要统计一下在n天中总共用了多少辆公交车。

现在的问题: 给定a₁,a₂,a₃…a_n和b₁,b₂,b₃…b_n，请你制定计划使得可用的公交车数最多（也就是这个计划的最优值）。计划中第一天可以选A，B公司中的任何一家。

Example: 假设 n=4 and a_i 和 b_i 分别为下面表中的值.

--------------------------------------------------------------------------
　　　　Day 1　　　　Day 2　　　　Day 3　　　Day 4
A　　　　11　　　　　 2　　　　　　2　　　　　　9
B　　　　4　　　　　　1　　　　　　21 　　　　　23
-------------------------------------------------------------------------

那么要使计划中可用公交车数最多，第一天要选A公司，第二天要更换公司，第三、四天都选者B公司。公交车数为 11+0+21+23=55.

Lx 对这个问题束手无策，所以他需要你的帮助。你要帮助他编一个有效的程序，当知道a₁,a₂,a₃…a_n和b₁,b₂,b₃…b_n的时候能算出计划的最优值来。

Input

第一行包含一个整数，表示测试实例的个数。每一个测试实例包含三行，第一行为一个正整数n(0<n<=1000000)表示天数；第二行包含a₁,a₂,a₃…a_n (0<a_i<=100)n个正整数，其中a_i为第i天A公司能提供的公交车数量；第三行包含b₁,b₂,b₃…b_n (0<b_i<=100)n个正整数，其中b_i为第i天B公司能提供的公交车数量。

Output

相应的每一行输出对应的实例的最优值。

Sample Input

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

Sample Output

55
21

Hint

huge input, scanf is recomended

Source

2008年绍兴市大学生计算机技能竞赛