시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 32 9 6 37.500%

문제

음 아닌 정수들로 이루어진 두 개의 집합 S와 T가 있다. S의 원소들과 T의 원소들을 짝지으려고 하는데, 다음과 같은 규칙을 만족하도록 하고 싶다.

1) S의 임의의 원소 s는 T의 어떤 원소와도 짝지어질 수 있다. 또한 T의 임의의 원소 t도 S의 어떤 원소와도 짝지어질 수 있다.

2) S의 모든 원소는 적어도 하나의 T의 원소와는 짝지어져야 하고, T의 모든 원소 역시 적어도 하나의 S의 원소와는 짝지어져야 한다.

예를 들어 S={2, 8, 9, 10, 11}, T={0, 3, 4, 6, 7, 11}을 보자. {(2, 0), (2, 3), (2, 4), (8, 6), (9, 7), (10, 11), (11, 11)}은 규칙을 만족하는 경우가 된다. 하지만 {(2, 0), (8, 3), (9, 4), (10, 6), (11, 7)}은 규칙을 만족하는 경우가 아닌데, T의 원소 11이 S의 어떤 원소와도 짝지어지지 않았기 때문이다.

각각의 짝 (a, b)의 비용이란, a와 b의 차이의 절대값으로 정의된다. 우리는 모든 비용의 합을 최소로 하도록 S의 원소들과 T의 원소들을 짝지으려 한다. 위에서 주어진 S와 T에 대해서는 10이 최소의 비용합이 된다.

S와 T가 주어지면, 모든 비용의 합을 최소로 하도록 S의 원소들과 T의 원소들을 짝지어 주는 프로그램을 작성하시오.

입력

첫째 줄에 S의 원소의 개수와 T의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 S의 원소, 셋째 줄에는 T의 원소가 첫째 줄에 주어진 개수만큼 빈 칸을 사이에 두고 증가하는 순서대로 주어진다. 각 집합의 원소의 크기는 500,000 이하이며, 주어지는 수는 0 이상 1,000,000,000 이하의 정수이다.

출력

첫째 줄에 최소의 비용합을 출력한다.

예제 입력

5 6
2 8 9 10 11
0 3 4 6 7 11

예제 출력

10

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Seoul 2007 J번

  • 문제를 번역한 사람: author5