Description

There is a stove in JOI's room. Since JOI is used to cold temperatures, when he is alone in his room, he does not need to turn on the stove. However, when there are guests, he needs to turn on the stove.

One day, $N$ guests will visit JOI. The $i$-th guest ($1 \leq i \leq N$) will arrive at time $T_i$ and leave at time $T_i + 1$. At any time, at most one guest visits JOI. JOI can turn the stove on or off at any time.

JOI uses matches to light the stove. JOI has only $K$ matches, so he can turn on the stove at most $K$ times. At the beginning of the day, the stove is off. When the stove is on, it consumes fuel. Therefore, JOI controls when to turn the stove on or off, and he wants to minimize the total running time of the stove.

Given the guest visit information and the number of matches JOI has, write a program to compute the minimum possible total running time of the stove.

Input Format

The first line contains two space-separated integers $N$ and $K$. This means that $N$ guests will visit JOI, and JOI has $K$ matches.

Each of the next $N$ lines contains an integer $T_i$ on the $i$-th line. This means that the $i$-th guest will arrive at time $T_i$ and leave at time $T_i + 1$.

Output Format

The only line should contain one integer: the minimum total running time of the stove.

3 2
1
3
6

4

3 1
1
2
6

6

3 3
1
3
6

3

10 5
1
2
5
6
8
11
13
15
16
20

12

Hint

Constraints

For $100\%$ of the testdata, $1 \leq N \leq 10^5$, $1 \leq K \leq N$, $1 \leq T_i \leq 10^9$ ($1 \leq i \leq N$), $T_i < T_{i+1}$ ($1 \leq i \leq N - 1$).

• Subtask $1$ ($20$ points): $N \leq 20$.
• Subtask $2$ ($30$ points): $N \leq 5000$.
• Subtask $3$ ($50$ points): No additional constraints.

Sample Explanation

For Sample $1$: Three guests will visit JOI. If he turns the stove on and off in the following way, the stove is on when guests visit, he turns on the stove twice, and the total running time is $(4 - 1) + (7 - 6) = 4$.

• When the first guest arrives, he turns on the stove at time $1$.
• When the second guest leaves, he turns off the stove at time $4$.
• When the third guest arrives, he turns on the stove at time $6$.
• When the third guest leaves, he turns off the stove at time $7$.

Since the total running time cannot be smaller than $4$, output $4$.

For Sample $2$: JOI can turn on the stove only once. Therefore, he turns on the stove at time $1$ when the first guest arrives, and he turns it off at time $7$ when the third guest leaves.
Note that a guest's leaving time may be the same as the next guest's arrival time.

For Sample $3$: JOI turns on the stove when each guest arrives, and turns it off when each guest leaves.

Problem Note

This problem comes from T1: Stove of The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round: T1: Stove.
Translated and整理 (zhengli) by @求学的企鹅.

Translated by ChatGPT 5