Problem Description

JOI-kun's room has a stove. Since JOI-kun is accustomed to cold temperatures, he does not need to turn on the stove when he is alone in the room. However, when he has guests, he needs to turn on the stove. On a certain day, $N$ guests will visit JOI-kun. The $i$-th guest ($1 \leq i \leq N$) will arrive at time $T_i$ and leave at time $T_i+1$. At any given time, there is at most one guest visiting JOI-kun. JOI-kun can turn the stove on or off at any time. JOI-kun uses matches to light the stove. He 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 requires fuel. Therefore, JOI-kun controls when he turns the stove on or off, aiming to minimize the total operating time of the stove.

Given the data of the guests visiting JOI-kun and the number of matches he has, write a program to calculate the minimum total operating time of the stove.

Input Format

The first line contains two space-separated integers $N$ and $K$. This means $N$ guests will visit JOI-kun, and JOI-kun has $K$ matches. The next $N$ lines contain an integer $T_i$ each. This means the $i$-th guest will arrive at time $T_i$ and leave at time $T_i+1$.

Output Format

The output should contain a single line with an integer representing the minimum total operating time of the stove.

Sample Input and Output

Sample Input #1

3 2
1
3
6

Sample Output #1

4

Sample Input #2

3 1
1
2
6

Sample Output #2

6

Sample Input #3

3 3
1
3
6

Sample Output #3

3

Sample Input #4

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

Sample Output #4

12

Notes/Hints

Data Size and Constraints

For $100\%$ of the data, $1 \leq N \leq 10^5$, $1 \leq K \leq N$, $1 \leq T_i \leq 10^9$ ($1 \leq i \leq N$), and $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-kun. If he turns on the stove when guests arrive and turns it off when they leave, he turns on the stove twice, and the total operating time of the stove 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 operating time of the stove cannot be less than $4$, the output is $4$.

For Sample #2: JOI-kun can only turn on the stove once. Therefore, he turns on the stove at time 1 when the first guest arrives and turns it off at time 7 when the third guest leaves.

Note that the time a guest leaves can be the same as the time the next guest arrives.

For Sample #3: JOI-kun turns on the stove when each guest arrives and turns it off when each guest leaves.

见题面 Input 部分

见题面 Output 部分