소 볼룸 댄스
면접 대비시간 제한1초메모리 제한1024 MB
남자 소 N마리와 여자 소 N마리를 한 쌍씩 짝지어 키 차이의 합이 가장 작아지는 값을 구합니다.
문제
소는 춤을 놀랄 만큼 못 춘다. 그럼에도 존 농부는 우아하게 춤추는 소일수록 우유를 더 많이 생산하는 경향이 있다는 것을 알아냈고, 그래서 농장의 소 전체를 볼룸 댄스 수업에 등록했다. 첫 수업에서는 N(1 ≤ N ≤ 1000)마리의 수소(불이라고도 부른다)와 N마리의 암소를 반드시 짝지어 커플로 만들어야 한다. 두 소의 키가 비슷하면, 즉 키 차이가 작으면 좋은 커플이다. 모든 소의 키가 주어질 때, 커플들의 키 차이 합이 최소가 되도록 짝짓는 방법을 찾아라.
입력
첫 줄에 정수 N이 주어진다. 2번째 줄부터 N+1번째 줄까지 각 줄에 수소의 키를 나타내는 정수가 하나씩 주어진다. N+2번째 줄부터 2N+1번째 줄까지 각 줄에 암소의 키를 나타내는 정수가 하나씩 주어진다.
출력
첫 줄에 "최적" 짝짓기에서의 키 차이 합을 정수 하나로 출력한다.
힌트
키가 2, 8, 5, 5인 수소 4마리와 키가 1, 4, 10, 7인 암소 4마리가 있다.
가장 좋은 짝짓기는 (키 기준으로) 2-1, 8-10, 5-4, 5-7이다. 이 짝짓기의 키 차이 합은 6이다.