시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 120 16 12 63.158%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력

3 2
12 50 81
27 73

예제 출력

23

힌트