Optimal Service Center Placement

You are given a set of houses located along a one-dimensional line. The positions of the houses are provided as a list of integers. Your task is to place k service centers such that the sum of distances from each house to its nearest service center is minimized.

For any contiguous subset of houses, if you place a service center at the median position, the total cost (i.e. sum of absolute distances) for that subset is minimized. In particular, for houses with indices from i to j, with median index \(m = \lfloor (i+j)/2 \rfloor\), the cost is given by:

[ cost(i,j)=\sum_{l=i}^{j} |positions[l] - positions[m]| ]

Your goal is to compute the minimum total cost when exactly k centers are optimally placed for all houses.

inputFormat

The input is given from standard input (stdin) and has the following format:

• The first line contains two integers n and k where n is the number of houses and k is the number of service centers.
• The second line contains n space-separated integers representing the positions of the houses.

outputFormat

Output a single integer which is the minimum possible sum of distances from every house to its nearest service center. This should be printed on standard output (stdout).

## sample

5 2
1 2 3 5 9

5

</p>