Minimizing Total Distance to Post Offices

The problem gives you a set of villages located on an integer line (representing a highway) and asks you to choose locations for building a given number of post offices such that the total distance from every village to its nearest post office is minimized.

Each village is represented by a unique integer coordinate, and the distance between two villages is defined as the absolute difference of their coordinates.

You are provided with the number of villages and the number of post offices to build. Your task is to compute the minimum possible sum of distances from each village to its nearest post office.

Hint: A dynamic programming solution with precomputed cost for serving any consecutive segment of villages will work well. For a segment of villages from index i to j (after sorting the positions), the optimal cost to cover that segment with one post office is minimized if the post office is built at the median village. In mathematical terms, if m is the median index, then the cost is given by
\(cost(i,j)=\sum_{l=i}^{j} |A[l]-A[m]| \).

inputFormat

The first line contains two integers N and K (1 ≤ K ≤ N ≤ 1000), representing the number of villages and the number of post offices to build respectively. The second line contains N distinct integers representing the positions of the villages. The positions may be in any order.

outputFormat

Output a single integer — the minimum possible sum of distances from every village to its nearest post office.

sample

5 3
1 2 3 4 5

2