Informatica Online Judge

  소방차 (Tiny) [2148 / 0864]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 13   Total Tried : 14


The Champion of this Problem (C++) : histeria - ms / 532byte
My Best Submission (C++) : N/A

[KOI 고등 전국본선]

Background

직선 위에 여러 개의 소방펌프가 있다. 여러 대의 소방차가 물을 채우기 위해서 급하게 이 직선 위에 정차했다.

펌프의 수는 소방차의 수 보다 크거나 같다. 그림에는 두 대의 소방차 (위치는 27과 73)가 세개의 펌프 (위치는 12, 50, 81) 사이에 정차 한 것을 보여주고 있다.



소방차에서 물을 채우기 위해 펌프와 소방차 호스를 연결한다.

시간을 절약하기 위해서 모든 소방차에 동시에 물을 채우려 한다. 하나의 펌프에는 하나의 소방차만 연결될 수 있다.

사용하는 호스의 길이는 펌프와 소방차 사이의 거리이다. 그림의 경우, 첫 번째 소방차는 첫 번째 펌프의 연결하고 (호스 길이 15) 두 번째 소방차는 세 번째 펌프와 연결하면 (호스 길이는 8) 사용하는 호스 길이의 합은 15+8 = 23 이다.

이렇게 하는 것이 호스 길이의 합을 최소로 한다.

펌프들의 위치와 소방차들의 위치가 주어질 때 호스 길이의 합을 최소로 하면서 펌프들을 소방차들에 연결하는 방법을 구하는 프로그램을 작성하시오.

Input

첫째 줄에는 펌프의 수를 나타내는 정수 P와 소방차의 수를 나타내는 F가 주어진다.

1 ≤ P ≤ 20 이고 1 ≤ F ≤ 20 이며 P≥F 이다.

둘째 줄에는 펌프들의 위치를 나타내는 서로 다른 P개의 정수가 오름차순으로 주어진다.

셋째 줄에는 소방차들의 위치를 나타내는 서로 다른 F개의 정수가 오름차순으로 주어진다.

펌프와 소방차가 같은 위치에 있을 수도 있다. 주어진 정수는 모두 100 이하의 양수이다.

Output

사용하는 호스 길이의 합을 출력한다. 출력 결과는 2^31 - 1 을 넘지 않는다.

IO Example

입력
3 2
12 50 81
27 73

출력
23

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]