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_{1}, …, t_{n},
followed by p_{1}, …, p_{n}.
Assume 1 ≤ n ≤ 10^{5},
and that all t_{i} and p_{i} are between 1 and 10^{9}.

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**

280 17 20 4000000000

Information

- Author
- Ferran Alet and Ángel García
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Setzè Concurs de Programació de la UPC - Semifinal
- Date
- 2018-06-20