Sensors

N sensors are installed along a highway. To collect and analyze the data from these sensors, at most K concentrators can be installed on the highway within the available budget.

Each concentrator can adjust the interval it can receive from. Its reception area is one connected interval on the highway. Every sensor must be able to communicate with at least one concentrator. To reduce maintenance cost, the sum of the lengths of all reception intervals must be minimized.

Assume the highway is a straight line on a plane. Each sensor is placed at an integer distance from a fixed origin on this line, so each sensor position is represented by one integer. Sensor coordinates do not have to be distinct. Using at most K concentrators, find the minimum possible sum of reception-area lengths needed to cover all sensors. The length of each reception area is at least 0.

The first line contains the number of sensors N (1 <= N <= 10,000).

The second line contains the maximum number of concentrators K (1 <= K <= 1,000).

The third line contains N sensor coordinates separated by spaces. Each coordinate is an integer whose absolute value is at most 1,000,000.

Print the minimum possible sum of reception-area lengths that allows all sensors to communicate when at most K concentrators are used.