Training for the World Finals P51803

Statement

thehtml

The UPC team 12 seconds could barely train for the World Finals. For instance, sometimes only Ferran and Ángel could join for a training. In those cases, a possible strategy was to make Ferran think about how to solve the problems, and to make Ángel program the solutions previously found and written down on paper by Ferran.

Supose that a training had n problems. Let t_i be the time that Ferran needed to solve the i-th problem, and p_i be the time that Ángel needed to program the i-th problem. Both Ferran and Ángel could only perform one task at a time, but could decide the order of thinking and the order of programming, with just one restriction: Ferran had to completely solve a problem before Ángel could start programming its solution.

Given all this information, can you please minimize the total time to solve and program all the problems?

Input

Input consists of several cases, each one with n followed by t₁, …, t_n, followed by p₁, …, p_n. Assume 1 ≤ n ≤ 10⁵, and that all t_i and p_i are between 1 and 10⁹.

Output

For every case, print the minimum time to solve and program all the problems.

Public test cases

Input

2
80 90
100 100

4
4 4 4 4
1 2 4 6

5
5 1 2 3 6
3 1 3 5 5

3
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

Output

Information

Author: Ferran Alet and Ángel García
Language: English
Official solutions: C++
User solutions: C++