Baltic Olympiad in Informatics: 2008 Day 2, Problem 3

In the dark basement of chemistry professor Acidrain's house there are two drawers with gloves — one with left hand and other with right hand gloves. In each of them there are gloves of ~n~ different colours. Professor knows how many gloves of each colour there are in each drawer (the number of gloves of the same colour may differ in both drawers). He is also sure that it is possible to find a pair of gloves of the same colour.

Professor's experiment may be successful only if he uses gloves of the same colour (it does not matter which one), so before every experiment he goes to the basement and takes gloves from the drawers hoping that there will be at least one pair of the same colour. It is so dark in the basement that there is no possibility to recognize colour of any glove without going out of the basement. Professor hates going to the basement more than once (in case there was no pair of gloves of the same colour), as well as bringing unnecessarily large amounts of gloves to the laboratory.

Calculate the smallest total number of gloves which must be taken to be sure that among them it is possible to find at least one pair of gloves of the same colour (it is necessary to specify the exact number of gloves to be taken from each drawer).

Constraints

~1 \le n \le 20~

~0 \le a_i, b_i \le 10^8~

Subtask 1 [40%]

~1 \le n \le 4~

~0 \le a_i, b_i \le 10~

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line of the standard input contains one positive integer ~n~ describing the number of distinct colours. The second line of input contains ~n~ space-separated integers ~a_1, a_2, \dots, a_n~, where ~a_i~ corresponds to the number of gloves of colour number ~i~ in the drawer with left hand gloves. Finally, the third line of input contains ~n~ space-separated integers ~b_1, b_2, \dots, b_n~, where ~b_i~ corresponds to the number of gloves of colour number ~i~ in the drawer with right hand gloves.

Output Specification

The first line of the output should contain an integer — the number of gloves which must be taken from the drawer with left hand gloves. The second line of output should contain an integer — the number of gloves which must be taken from the drawer with right hand gloves. The sum of these two numbers should be as small as possible. If there are several correct results, your program should output any of them.

Sample Input

4
0 7 1 6
1 5 0 6

Sample Output

2
8

Explanation

By taking ~2~ gloves from the left drawer, he is guaranteed to at least have one of colours ~2~ or ~4~. By taking ~8~ gloves from the right hand drawer, he is guaranteed to have at least one glove of colour ~2~ and ~4~.