Post Office Problem

Given a set of villages located along a highway, which is represented by the integer number line, each village is marked by a unique integer coordinate. The distance between any two positions is defined as the absolute difference of their coordinates, i.e. \(|x-y|\). The task is to construct a given number of post offices on some (but not necessarily all) of these villages such that the total distance from every village to its nearest post office is minimized.

You are given the positions of the villages and the number of post offices to be built. Your goal is to compute the minimum possible sum of distances from each village to its nearest post office.

Mathematically, if the villages' positions are \(v_1, v_2, \dots, v_n\) (with \(v_i \neq v_j\) for \(i \neq j\)) and you need to choose \(k\) post offices, you want to minimize the sum:

[ S = \sum_{i=1}^{n} \min_{j=1}^{k} \lvert v_i - p_j \rvert, ]

where \(p_j\) are the positions (chosen among the villages) where the post offices are built.

inputFormat

The input is given in two lines:

• The first line contains two integers \(n\) and \(k\) (with \(1 \leq k \leq n\)), where \(n\) is the number of villages and \(k\) is the number of post offices to build.
• The second line contains \(n\) distinct integer coordinates of the villages (not necessarily sorted).

Input is read from the standard input.

outputFormat

Output a single integer representing the minimum possible sum of distances from every village to its nearest post office. Output the result to the standard output.

sample

5 3
1 2 3 4 5

2