Patrol Optimization

There are n points along a line that need to be patrolled. The headquarters plans to dispatch k sentinels to complete the task. Each sentinel can choose any starting position freely (without consuming any energy). However, when a sentinel moves one unit distance (either from i to i+1 or from i to i-1), it consumes 1 unit of energy.

The goal is to assign the k sentinels so that:

• Every patrol point is visited by at least one sentinel.
• The total energy consumption is minimized.

Assuming that the positions of the patrol points are given by a sequence of integers, let the sorted positions be \(a_1, a_2, \dots, a_n\). If a single sentinel is used to cover a contiguous segment from \(a_i\) to \(a_j\), the minimum energy required is

\[ \text{energy} = a_j - a_i \]
since the sentinel can start at one end without cost and then traverse to the other end. With multiple sentinels, one may place splits between points. For k sentinels, one can choose \(k-1\) gaps to avoid, and the minimum total energy required becomes

\[ \text{total energy} = a_n - a_1 - \sum_{i=1}^{k-1} g_i, \]
where \(g_i\) are the \(k-1\) largest differences between consecutive patrol points.

inputFormat

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 10⁵), representing the number of patrol points and the number of sentinels, respectively.

The second line contains n integers, representing the positions of the patrol points on the line. These positions are not necessarily in sorted order and can range over a reasonable integer domain.

outputFormat

Output a single integer: the minimum total energy consumption for the sentinels to ensure every patrol point is covered at least once.

sample

6 2
1 6 9 3 2 13

8