Training for the World Finals P51803

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, \dots, t_n$, followed by $p_1, \dots, p_n$. Assume $1 \le n \le 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.