z-McZ
Mr. Little Z is launching his own chain of fast food restaurants - McZ. As an introductory offer, he plans to offer free home delivery to all the customers on the same road as the restaurant. It is a straight road with plots alongside the road. The road is represented as an integer axis, and the position of each plot is identified with a single integer coordinate. There are no two plots in the same position.
The distance between two positions is the absolute value of the difference of their integer coordinates. Outlets will be built in some, but not necessarily all of the plots. A plot and the outlet in it have the same position.
For building the outlets, their positions should be chosen so that the total sum of all distances between each plot and its nearest outlet is minimum. Help Mr. Z find the least possible sum of all distances between each plot and its nearest outlet.
The first line of the standard input contains two integers: the first is the
number of plots Pl, 1 <= Pl <=300, and the second is the number of outlets O,
1<=O<=30, O<=Pl. The second line contains Pl integers in increasing order. These Pl integers are the positions of the plots. For each position X it holds that 1<=X<=10000.
To the standard output write the minimum sum of all distances between each plot and its nearest outlet.
Sample Input:
5 1
1 2 3 4 5Sample Output:
6If the outlet is at 3, |1-3| + |2-3| + |4-3| + |5-3| = 6
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.