맥주 마라톤
시간 제한2초메모리 제한512 MB
N개의 맥주 부스 위치와 고정 간격 K가 주어질 때, 시작점을 자유롭게 정해 등차수열 위치로 옮길 때 모든 부스의 총 이동 거리를 최소로 만드는 값을 구한다.
문제
매년 열리는 맥주 마라톤의 부스 버전에서는 트랙을 따라 여러 맥주 부스(맥주 가판대, 맥주 스탠드라고도 한다)가 설치된다. 모든 참가자는 서로 다른 맥주 부스를 정해진 횟수만큼 방문해야 한다. 이웃한 두 맥주 부스 사이의 거리는 모두 정확히 같아야 하며, 대회 규정에 명시된 특정 값과 일치해야 한다.
맥주 부스 설치를 맡은 업체는 (과도한 비용을 받고도) 일을 대충 해서 맥주 부스들을 트랙을 따라 거의 임의의 위치에 남겨 둔 채 마을을 떠났다. 다행히 최신 AI 기술 덕분에, 이 업체는 트랙의 특정 기준점을 기준으로 측정한 맥주 부스의 정확한 위치를 미터 단위로 보고할 수 있었다. 마라톤 조직위원회는 자원봉사자들을 보내 맥주 부스들을 대회 규정에 맞는 새 위치로 옮기려 한다.
조직위원회는 모든 맥주 부스를 옮겨야 하는 총 거리(미터)를 최소화하려 한다. 경주의 출발선과 결승선은 맥주 부스의 최종 위치에 따라 나중에 정한다.
입력
첫째 줄에는 두 정수 N과 K가 주어진다(1 ≤ N, K ≤ 106). N은 맥주 부스의 개수이고, K는 이웃한 맥주 부스 사이의 규정 거리이다. 둘째 줄에는 N개의 서로 다른 정수 x1, . . . , xN이 주어진다(−106 ≤ xi ≤ 106). 이는 기준점을 기준으로 한 맥주 부스의 원래 위치를 미터 단위로 나타낸 것이다. 양수는 기준점을 지난 위치를, 음수는 기준점 이전의 위치를 가리킨다.
출력
대회 규정을 만족하도록 맥주 부스들을 옮겨야 하는 최소 총 거리(미터)를 정수 하나로 출력한다.