2013年7月23日 星期二

11269 - Setting Problems


設計程式競賽的題目是件困難的工作,有很多事情要做,如出題目、題目解答、測試數據以、驗證題目描述以及撰寫多組解的程式 ... 等。

在一場名為 "If you can not crash judges by solutions, crash contestants by problems" 的競賽中被賦予出題目的責任, Sultan 和 GolapiBaba 將負責出題,他們決定在這場競賽出 N 道題目,而首先由 Sultan 創建題目描述、題目解答及測試數據,而當他完成該題目時,緊接著由 GolapiBaba 負責驗正題目描述以及撰寫多組解的程式。

然而這工作耗費多時,而且不會有一個人手上同時執行多個題目的編寫,特別注意 GolapiBaba 一定要等到 Sultan 將題目完成後,才能開始動作該題的驗證工作。

寫一個程式安排順題編寫的順序,使得 Sultan 和 GolapiBaba 在最少的時間內完成所有題目。 

Input

輸入最多 50 組測資,每組測資第一行會有一個整數 N (1 <= N <= 20),表示有多少題目。

接著會有 N 個整數 Si (1 <= Si <= 1001 <= i <= N),表示 Sultan 完成第 i 題的工作時間。
以及會有 N 個整數 Gi (1 <= Gi <= 1001 <= i <= N),表示 Golapibaba 完成第 i 題的工作時間。

Output

輸出完成所有題目的最少時間。

Sample Input
Sample Output
3
8 1 6
1 6 3
3
4 5 6
1 1 6

16
16


Problemsetter: Mohammad Mahmudur Rahman
Special Thanks To: Abdullah Al Mahmud