큰 길이 직선으로 쭉 뻗어있고, 길 옆으로 여러 마을이 자리잡고 있다. 이 문제에서는 큰 길은 정수가 늘어서는 수평선이고, 각 마을의 위치는 수평선 위의 한 점으로 표현된다. 마을들의 좌표가 겹치는 경우는 없다. 마을 사이의 거리는 수평선 상에 있는 좌표의 차이의 절대값으로 정의 된다.
우리는 이들 마을이 있는 곳에 우체국을 몇 곳 지으려고 한다. 물론 모든 마을마다 다 짓는 것은 아니다. 전체 마을 중 몇 곳을 골라, 그 위치에만 우체국을 짓게 된다. 그리고 우리는 각 마을과 그 마을과 가장 가까운 우체국 사이의 거리의 합이 최소가 되게 하고 싶다.
각 마을의 위치와 짓고자 하는 우체국 개수를 입력으로 받는다. 그래서 각 마을과 그 마을과 가장 가까운 우체국 사이 거리의 합으로 있을 수 있는 최소값을 계산하고, 그런 결과를 낼수 있도록 각 우체국을 지을 위치를 출력하는 프로그램을 작성하시오.
제한 시간은 2 초이다.
입력 10 5 1 2 3 6 7 9 11 22 44 50 출력 9
출처 : ioi 기출