Problem7375--独立任务最优调度问题

7375: 独立任务最优调度问题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

用 2 台处理机 A 和 B 处理 n 个作业。
设第 i 个作业交给机器 A 处理时需要时间 $a_i$,若由机器 B 来处理,则需要时间 $b_i$。
既不能将一个作业分开由 2 台机器处理,也没有一台机器能同时处理 2 个作业。
设计一个算法,使得这 2 台机器处理完这 n 个作业的时间最短,从任何一台机器开工到最后一台机器停工的总时间。

Input

输入的第一行是一个正整数 $n$,表示要处理 $n$ 个作业。
接下来的 2 行中,每行有 $n$ 个正整数,分别表示处理机 A 和 B 处理第 i 个作业需要的处理时间。

Output

输出最短处理时间。

Sample 1 Input

6
2 5 7 10 5 2
3 8 4 11 3 4

Sample 1 Output

15

Source/Category