文理学院程序设计在线练习


车辆安排

Time Limit: 4 Second(s)    Memory Limit: 32 MB

Total Submission(s): 62   Accepted Submission(s): 34
Problem Description

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

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

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

现在的问题: 给定a1,a2,a3…an和b1,b2,b3…bn,请你制定计划使得可用的公交车数最多(也就是这个计划的最优值)。计划中第一天可以选A,B公司中的任何一家。

Example: 假设 n=4 and ai 和 bi 分别为下面表中的值.
--------------------------------------------------------------------------
    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 对这个问题束手无策,所以他需要你的帮助。你要帮助他编一个有效的程序,当知道a1,a2,a3…an和b1,b2,b3…bn的时候能算出计划的最优值来。

Input

第一行包含一个整数,表示测试实例的个数。每一个测试实例包含三行,第一行为一个正整数n(0<n<=1000000)表示天数;第二行包含a1,a2,a3…an (0<ai<=100)n个正整数,其中ai为第i天A公司能提供的公交车数量;第三行包含b1,b2,b3…bn (0<bi<=100)n个正整数,其中bi为第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年绍兴市大学生计算机技能竞赛