큰길이 직선으로 쭉 뻗어있고, 길 옆으로 여러 마을이 자리잡고 있다.

이 문제에서 큰길은 정수가 늘어서 있는 수평선이고, 각 마을의 위치는 수평선 위의 한 점으로 표현된다.

마을들의 좌표가 겹치는 경우는 없다. 두 마을 사이의 거리는 수평선상에 있는 좌표의 차이의 절대값으로 정의된다.

우리는 이들 마을이 있는 곳에 소방서를 몇 곳 지으려고 한다. 물론 모든 마을마다 다 짓는 건 아니다.

전체 마을 중 몇 곳을 골라, 그 위치에만 소방서를 짓게 된다. 이 때 아래 비용이 최소가 되도록 소방서를 지으려고 한다.

(각 마을과 그 마을과 가장 가까운 소방서 사이의 거리의 합) + K × (소방서의 개수)

마을의 정보가 주어지면 조건을 만족하도록 적절히 소방서를 짓는 프로그램을 작성하여라.

소방서 timer 1s memory 125MB

소방서 1s 125MB