짝맞추기

문제 정보

문제

유명 단체 미팅 주선회사 ACM(Ansp Couple Manager)이 낮은 성공률로 인해 부도 위기에 몰려있다! ACM의 사장인 LIBe는 유명 기밀 정보 수집가 Kogle에게 남아있는 ACM 자산의 상당분을 지급하고, 한창 잘나가는 astein이 사장으로 있는 ICPC(Intensive Complete Perfect Couple)의 정보를 빼내 오라고 지시하였다. 하지만 ICPC의 보안은 치밀했고, Kogle은 모든 정보를 완전히 빼내 오는데 실패하였다. 하지만 ICPC가 잘 나갈 수밖에 없는 원인을 알아내게 되었다.

보고 있으면 무언가 떠오르는 회사의 이름답게, ICPC는 회원들의 수치를 정수로 모델링 한 다음, 짝을 짓는 남녀간의 수치의 차이의 합을 최소화 하는 알고리즘을 사용하고 있었다.

LIBe는 실제 커플 성사율이 90%를 육박하는 ICPC사의 알고리즘을 당장 사용하고자 하였지만, Kogle이 그 알고리즘까지는 알아내지 못했다. 고민 끝에 LIBe는 프로그래밍 경시대회에서 두각을 나타내고 있는 당신에게 풍선을 대가로 남녀간의 수치의 차이의 합을 최소화하는 프로그램을 구현해 달라고 요청하였다. LIBe가 요청한 프로그램을 구현하여 (더군다나 자기 자신도 안생겨서 슬퍼하는) LIBe에게 조금이나 위안을 주자.

남성과 여성의 수는 동일하며, 동성간이 짝을 짓는 경우는 고려하지 않으며, 모든 사람은 반드시 짝을 지어야 하고, 한 사람이 두 명과 짝을 짓는 경우는 없다.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 T(1 <= T <= 50)가 주어진다.
테스트 케이스의 첫 번째 줄에는 ACM에서 주최하는 단체 미팅에 등록한 남녀 회원의 수 N(1 <= N <= 10,000)이 주어진다.

테스트 케이스의 두 번째 줄에는 남성 회원의 수치를 나타내는 N개의 정수가 주어지고,
세 번째 줄에는 여성 회원의 수치를 나타내는 N개의 정수가 주어진다.

이 수치는 절대값이 1,000을 넘지 않는 정수이며, 각 수치 사이는 공백으로 구분된다.

출력

각 테스트 케이스에 대해서 짝을 짓는 남녀간의 수치의 차이의 합의 최소값을 한 줄에 하나씩 출력한다.

예제 입력

2
4
1 2 3 4
8 6 7 5
3
-1 0 1
-1 -1 -1

예제 출력

16
3

노트

9개의 댓글이 있습니다.