|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||7||1||1||14.286%|
In the booths version of the popular annual Beer Marathon, many beer booths (also called beer stalls or beer stands) are installed along the track. A prescribed number of visits to different beer booths is a part of the race for all contestants. The distances between any two consecutive beer booths should be exactly the same and equal to the particular value specified in the race rules.
The company responsible for beer booths installation did the sloppy work (despite being excessively paid), left the beer booths on more or less random positions along the track and departed from the town. Fortunately, thanks to advanced AI technology, the company was able to report the exact positions of the beer booths along the track, measured in meters, with respect to the particular anchor point on the track. The marathon committee is going to send out the volunteers to move the beer booths to new positions, consistent with the race rules.
They want to minimize the total number of meters by which all beer booths will be moved. The start line and the finishing line of the race will be chosen later, according to the resulting positions of the beer booths.
The first line of input contains two integers N and K (1 ≤ N, K ≤ 106), where N is the number of beer booths and K is the prescribed distance between the consecutive beer booths. The second line of input contains N pairwise different integers x1, . . . , xN (−106 ≤ xi ≤ 106), the original positions, in meters, of the beer booths relative to the anchor point. The positive values refer to the positions past the anchor point and the negative values refer to the positions before the anchor point.
Output a single integer — the minimal total number of meters by which the beer booths should be moved to satisfy the race rules.
3 1 2 5 7
10 4 140 26 69 55 39 64 2 89 78 421