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

펌프의 수는 소방차의 수 보다 크거나 같다.

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

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

시간을 절약하기 위하여 모든 소방차에 동시에 물을 채우려 한다.

하나의 펌프에는 하나의 소방차만 연결할 수 있다. 사용하는 호스의 길이는 펌프와 소방차 사이의 거리이다.

그림의 경우, 첫 번째 소방차는 첫 번째 펌프에 연결하고 (호스 길이는 15),

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

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

펌프들의 위치와 소방차들의 위치가 주어질 때,

호스 길이의 합을 최소로 하면서 펌프들을 소방차들에 연결하는 방법을 구하는 프로그램을 작성하시오.

소방차 timer 1초 memory 256MB

소방차 1초 256MB