Post Office Placement Problem

There are \(n\) villages located alongside a highway, which is represented by the integer axis. Each village is identified by an integer coordinate, and the distance between any two villages is defined as the absolute difference of their coordinates.

You are required to build \(m\) post offices. The post offices must be built in some of the villages (not necessarily in all of them). The positions for the post offices should be chosen in such a way that the sum of the distances from each village to its nearest post office is minimized.

Formally, let the village coordinates after sorting be \(x_1, x_2, \dots, x_n\). If we choose a set \(S\) of \(m\) villages to have post offices, the objective is to minimize \[ \sum_{i=1}^{n} \min_{s \in S} |x_i - s|. \]

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le m \le n)\), representing the number of villages and the number of post offices to be built respectively.

The second line contains \(n\) space-separated integers, representing the coordinates of each village. These coordinates may not be in sorted order.

outputFormat

Output a single integer representing the minimal possible sum of the distances between each village and its nearest post office.

sample

3 1
-1 1 3

4