문제
큰길이 직선으로 쭉 뻗어있고, 길 옆으로 여러 마을이 자리잡고 있다.
이 문제에서 큰길은 정수가 늘어서 있는 수평선이고, 각 마을의 위치는 수평선 위의 한 점으로 표현된다.
마을들의 좌표가 겹치는 경우는 없다. 두 마을 사이의 거리는 수평선상에 있는 좌표의 차이의 절대값으로 정의된다.
우리는 이들 마을이 있는 곳에 소방서를 몇 곳 지으려고 한다. 물론 모든 마을마다 다 짓는 건 아니다.
전체 마을 중 몇 곳을 골라, 그 위치에만 소방서를 짓게 된다. 이 때 아래 비용이 최소가 되도록 소방서를 지으려고 한다.
(각 마을과 그 마을과 가장 가까운 소방서 사이의 거리의 합) + K × (소방서의 개수)
마을의 정보가 주어지면 조건을 만족하도록 적절히 소방서를 짓는 프로그램을 작성하여라.
입력
첫 번째 줄에는 마을의 수 N (1 ≤ N ≤ 100,000)과 소방서 하나를 짓는 데 필요한 비용 K (1 ≤ K ≤ 109)이 주어진다.
두 번째 줄에는 각 마을의 위치를 나타내는 N개의 정수 좌표가 주어진다. 좌표는 오름차순으로 정렬되어 있으며 1 이상 109 이하이다.
출력
소방서를 적절히 지었을 때 비용을 출력한다.
예제
4 2
1 2 3 4
6
로그인해야 코드를 작성할 수 있어요.