소방차

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

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

소방차에 물을 채우기 위해 펌프와 소방차 사이를 호스로 연결한다. 시간을 절약하기 위하여 모든 소방차에 동시에 물을 채우려 한다. 하나의 펌프에는 하나의 소방차만 연결할 수 있다. 사용하는 호스의 길이는 펌프와 소방차 사이의 거리이다.

그림의 경우, 첫 번째 소방차는 첫 번째 펌프에 연결하고 (호스 길이는 15), 두 번째 소방차는 세 번째 펌프와 연결하면 (호스 길이는 8), 사용하는 호스 길이의 합은 \(23=15\)+8이다. 이렇게 하는 것이 호스 길이의 합을 최소로 한다.

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

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.

첫째 줄에는 펌프의 수를 나타내는 정수 P와 소방차의 수를 나타내는 정수 F가 주어진다. \(1 \le P \le 100{,}000\) 이고 \(1 \le F \le 100{,}000\) 이며, \(P \ge F\) 이다. 둘째 줄에는 펌프들의 위치를 나타내는 서로 다른 P개의 정수가 증가하는 순서로 주어진다. 셋째 줄에는 소방차들의 위치를 나타내는 서로 다른 F개의 정수가 증가하는 순서대로 주어진다. 펌프와 소방차가 같은 위치에 있을 수도 있다. 주어지는 정수는 모두 1,000,000 이하의 양수이다.

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

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2005 > 2차 대회 > 고등부 4번