3204 - 流水作业调度

给定n个作业,每个作业都需要先在M1机器上处理,然后再在M2两台机器上处理之后,才算处理完毕。第i个作业在M1上的处理时间为ai,在M2上的处理时间为bi。从M1处理第一个作业开始,到M2处理最后一个作业结束,称为作业周期。

问题为,如何安排作业顺序,使得作业周期最短。

输入

第一行为一个数n。 第二行为n个数,分别为a1,…,an。 第二行为n个数,分别为b1,…,bn。

输出

完成这n个作业所需要的最短时间。

样例

输入

3
2 3 5
6 3 4

输出

15

输入

4
3 4 8 10
6 2 9 15

输出

38

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题