题目描述

太空梯的装配使用了两台巨形机器$\red{A}$和$\red{B,}$现有$\red{n}$个作业要处理。设第$\red{i}$个作业交给 机器$\red{A}$处理时需要时间$\red{a_i,}$若由机器$\red{B}$来处理,则需要时间$\red{b_i}$。由于各作业的特点和机器 的性能关系,很可能对于某些$\red{i,}$有$\red{a_i≥}$$\red{b_i,}$而对于某些$\red{j,j≠}$$\red{i,}$有$\red{a_j<b_j}$。既不能将一个作业 分开由$\red{2}$台机器处理,也没有一台机器能同时处理$\red{2}$个作业。

对于给定的$\red{2}$台处理机$\red{A}$和$\red{B}$处理$\red{n}$个作业，找出一个最优调度方案,使$\red{2}$台机器处 理完这$\red{n}$个作业的时间最短。

输入格式

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

输出格式

输出最短处理时间。

样例

输入样例

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

输出样例

15

提示：

$\red {n <= 30 }$

所有的$\red{a_i <= 30}$