P2242 Highway Maintenance Problem

Due to long-term lack of maintenance, there are $n$ potholes on Country A’s highway. To repair these $n$ potholes quickly, Country A decides to impose traffic control on $m$ segments of the road. For simplicity, assume there is only one highway, and it is straight. Given the positions of the $n$ potholes, compute the minimal total length of road that must be under traffic control.

The input consists of two lines. - The first line contains two positive integers $n, m$ ($2 \le m \le n \le 15000$). - The second line contains the coordinates of the $n$ potholes (each within the 64-bit signed integer range), given in strictly increasing order with no duplicate coordinates.

Output a single line: the minimal total length.

[Sample Explanation] The controlled segments are: $3-8, 14-21, 25-31, 40-43$. Translated by ChatGPT 5