Description

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.

Input Format

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 Format

Output a single line: the minimal total length.

18 4
3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43

25

Hint

[Sample Explanation]

The controlled segments are: $3-8, 14-21, 25-31, 40-43$.

Translated by ChatGPT 5