Minimizing Traffic Control Length

Due to long‐time neglect, there are n potholes along Country A's highway. To quickly repair these potholes, the government decided to impose traffic control on m sections of the highway. The highway is assumed to be a single straight line.

Given the positions of the n potholes, your task is to determine the minimum total length of road that must be subjected to traffic control in order to cover all potholes.

Problem Analysis:
This problem can be solved by first sorting the pothole positions. If m is greater than or equal to n, each pothole can be controlled separately, resulting in zero control length. Otherwise, the idea is to cover consecutive positions with one controlled segment. The total control length of a segment covering potholes is the difference between its maximum and minimum positions. By identifying the largest gaps between consecutive potholes and treating them as boundaries between segments, you can minimize the overall control length.

Mathematical formulation:
If the sorted positions are \(p_1, p_2, \dots, p_n\), the initial total length is \(p_n - p_1\). Let the differences between consecutive positions be \(d_i = p_{i+1} - p_i\) for \(1 \leq i \leq n-1\). By selecting the \(m-1\) largest gaps and excluding them, the minimum required control length is:

\(\text{result} = (p_n - p_1) - \sum_{i=1}^{m-1} d_{(i)}\)

inputFormat

The first line contains two integers n and m (1 ≤ m ≤ n ≤ 10⁵), where n is the number of potholes and m is the number of traffic control segments available.

The second line contains n integers representing the positions of the potholes along the highway. Each position is a non-negative integer not exceeding 10⁹.

outputFormat

Output a single integer which is the minimum total length of the highway that must be under traffic control.

sample

6 2
1 6 9 3 6 7

5