Bovine Ballroom Dancing

Interview

Time limit1sMemory limit1024 MB

Summary

Pair each boy cow with a girl cow so the total height difference is as small as possible, and print that minimum sum.

Level: Easy3 of 10
Topics: Sorting, Greedy
Solved: No attempts yet

문제

Cows are remarkably bad dancers. Still, Farmer John found that graceful cows tend to produce more milk, so he enrolled his entire herd in a ballroom dance class. In the first class meeting, the N (1 ≤ N ≤ 1,000) boy cows (also called bulls) and N girl cows must be paired up into couples. Two cows make a good couple if their heights are similar, meaning the difference between their heights is small. Given the heights of all the cows, find a pairing that minimizes the total sum of height differences over all couples.

입력

Line 1: The single integer N. Lines 2 to N+1: Each line contains an integer giving the height of a boy cow. Lines N+2 to 2N+1: Each line contains an integer giving the height of a girl cow.

출력

Line 1: A single integer giving the sum of height differences in an "optimal" pairing.

힌트

There are 4 boy cows with heights 2, 8, 5, and 5, and 4 girl cows with heights 1, 4, 10, and 7.

The best pairing is 2-1, 8-10, 5-4, 5-7 (by height). The total sum of height differences for this pairing is 6.

Examples1

Example 1
Input
```
4
2
8
5
5
1
4
10
7
```
Expected output
```
6
```