Minimizing Stove Operation Time

JOI has a stove in his room. He only needs to turn it on when he has guests. On a certain day, there will be \(N\) guests. The \(i\)-th guest (\(1 \le i \le N\)) arrives at time \(T_i\) and leaves at time \(T_i+1\). It is guaranteed that at most one guest is present at any time.

At the beginning of the day, the stove is off. JOI can switch the stove on or off at any time. However, he uses a match to start (turn on) the stove and he has only \(K\) matches, meaning he can only turn on the stove at most \(K\) times. When the stove is on, it consumes fuel, so JOI wants to minimize the total time that the stove is running while ensuring that it is on for every period when a guest is present.

Note that if the stove is kept on between guest visits, it might run for extra time when no guest is there. In order to optimize the running time given the constraint on the maximum number of times the stove can be turned on, JOI may merge several guest intervals into one continuous period. If a guest interval is merged with the next one, the stove will run continuously including the gap between their required periods.

The problem is to choose the optimal times to turn the stove on/off (using at most \(K\) on operations) such that the stove covers all guest intervals while minimizing its total running time.

Hint: If the guest arrival times (\(T_1, T_2, \ldots, T_N\)) are sorted, then without merging the total running time is \(N\) (each interval has length 1). When intervals are merged the stove runs from the start of the first interval to the end of the last interval in that merge. The problem can be solved by considering the gaps between consecutive intervals. Let the gap between intervals \(i\) and \(i+1\) be \(T_{i+1} - (T_i+1)\). If all intervals are merged into a single continuous period, the running time would be \(T_N+1 - T_1\). However, one can reduce the running time by splitting at the largest gaps (using additional matches) so that the total running time is minimized. Formally, if we are allowed to have \(K\) segments, then the minimal total running time is given by:

\(\text{Total Time} = \bigl(T_N+1 - T_1\bigr) - \sum_{j=1}^{K-1} g_j\)

where \(g_j\) are the \(K-1\) largest gaps (if \(K < N\)); if \(K \ge N\), the answer is \(N\) (since each interval can be handled separately).

inputFormat

The first line contains two integers \(N\) and \(K\) separated by a space, where \(N\) is the number of guests and \(K\) is the maximum number of times the stove can be turned on.

The second line contains \(N\) space separated integers \(T_1, T_2, \ldots, T_N\) representing the arrival times of the guests. It is guaranteed that these times are given in strictly increasing order.

outputFormat

Output a single integer representing the minimum total time that the stove must be running to accommodate all guests.

sample

3 1
3 5 8

6