200% 190% 180% 170% 160% 150% 140% 130% 120% 110% 100%

Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

acm

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

cz

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2019

Beer Marathon

marathon.c, marathon.cpp, Marathon.java, marathon.py

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 exces-

sively 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.

Input Specification

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 Specification

Output a single integer -- the minimal total number of meters by which the beer booths should

be moved to satisfy the race rules.

Sample Input 1

Output for Sample Input 1

31

3

257

Sample Input 2

Output for Sample Input 2

10 4

511

140 26 69 55 39 64 2 89 78 421