Statement

This problem's maximum score is 50. This is a hard version.

Ninetail is a fox girl. She has some gloves in different colors. She has two drawers. So she put all the left-hand gloves into drawer #1 and all the right-hand gloves into drawer #2.

One day, she decided to take out A gloves randomly from drawer #1 and B gloves randomly from drawer #2. Question: what's the minimum A+B so that Ninetail will be able to get a pair of gloves of the same color for sure ? You need to print A and B.

Input

The first line contains integer N. The number of colors.

Then the second line contains A1...AN. The number of gloves of each colors in drawer 1

Then the third line contains B1...BN. The number of gloves of each colors in drawer 2

Output

A and B. One in a line. If there are many answers, print any.

Example

[Input]
4
0 7 1 6
1 5 0 6
[Ouput]
2
8

Subtask

$1\leq N\leq 20,0\leq Ai,Bi\leq 10^8$

For some testcases, $1\leq N\leq 4,0\leq Ai,Bi\leq 10$

You DON'T need to pass all testcases to get score