Tandem Bicycle

Interview

Time limit2sMemory limit512 MB

Summary

Pair each Dmojistan rider with a Pegland rider to minimize or maximize the sum of the larger speed in each pair.

Level: Medium4 of 10
Topics: Greedy, Sorting, Array, Math
Solved: No attempts yet

Problem

The citizens of Dmojistan and Pegland have been at war since time immemorial. They have finally signed a truce, and to celebrate it they will ride tandem bicycles together. $N$ citizens come from each country, and they must be assigned to pairs so that every pair holds one person from Dmojistan and one person from Pegland.

Every citizen has a cycling speed. In a pair the faster person always operates the tandem bicycle while the slower person sits and enjoys the ride. If the two members of a pair have speeds $a$ and $b$ , the bike speed of that pair is $\max(a, b)$ . The total speed is the sum of the bike speeds of the $N$ pairs.

Depending on the question number you are given, answer one of these.

Question 1: over all possible assignments into pairs, what is the minimum total speed?
Question 2: over all possible assignments into pairs, what is the maximum total speed?

Input

The first line contains the number of the question to solve. It is either 1 or 2.

The second line contains $N$ . ( $1 \le N \le 100$ )

The third line contains the speeds of the $N$ citizens of Dmojistan, separated by spaces.

The fourth line contains the speeds of the $N$ citizens of Pegland, separated by spaces.

Every speed is an integer between 1 and 1,000,000.

Output

Print on one line the minimum or the maximum total speed that answers the question.

Examples3

Example 1
Input
```
1
3
5 1 4
6 2 4
```
Expected output
```
12
```
Example 2
Input
```
2
3
5 1 4
6 2 4
```
Expected output
```
15
```

Example 3

Input

2
5
202 177 189 589 102
17 78 1 496 540

Expected output