Description

A chemistry professor named “Acid Rain” has a dark basement with two drawers of gloves: one drawer contains left-hand gloves, and the other contains right-hand gloves. Each drawer has gloves in $n$ different colors. The professor knows how many gloves of each color are in each drawer (the counts for the same color may differ between the two drawers). It is guaranteed that he can find at least one pair of gloves of the same color.

An experiment can succeed only if the professor wears a pair of gloves of the same color (the color does not matter). Therefore, before each experiment he goes to the basement to take gloves from the drawers, hoping to get at least one same-colored pair. However, the basement is so dark that he cannot distinguish the colors of any gloves unless he leaves the basement. The professor hates going to the basement more than once, and also hates bringing a large pile of gloves back to the lab (in case there is no same-colored pair).

Task

Write a program that:

• reads from standard input the number of colors and the number of gloves of each color;
• computes the minimum total number of gloves that must be taken to guarantee that among the taken gloves there is at least one pair of the same color (and you must specify the exact number of gloves taken from each drawer);
• writes the result to standard output.

Input Format

The first line of standard input contains a positive integer $n$, the number of different colors. The colors are numbered from $1$ to $n$.

The second line contains $n$ non-negative integers $a_1,a_2,\cdots ,a_n$, where $a_i$ is the number of gloves of color $i$ in the left-hand glove drawer.

The third line contains $n$ non-negative integers $b_1,b_2,\cdots ,b_n$, where $b_i$ is the number of gloves of color $i$ in the right-hand glove drawer.

Output Format

The first line of standard output contains a single integer: the number of gloves taken from the left-hand glove drawer. The second line contains a single integer: the number of gloves taken from the right-hand glove drawer. The sum of these two numbers should be as small as possible.

If there are multiple correct answers, your program may output any one of them.

4
0 7 1 6
1 5 0 6

2
8

Hint

For $40\%$ of the testdata, $n\le 4$ and $a_i,b_i\le 10$.

For all testdata, $1\le n\le 20$ and $0\le a_i,b_i\le 10^8$.

Translated by ChatGPT 5