Problem Description

JOI-kun's room has a stove. JOI-kun himself is resistant to cold, so he doesn't need to turn on the stove when he is alone in the room, but he needs to turn it on when there are guests.

On this day, there will be $N$ guests visiting JOI-kun's room. The $i$-th ($1 \leq i \leq N$) guest arrives at time $T_i$ and leaves at time $T_i + 1$. There will never be multiple guests at the same time.

JOI-kun can turn the stove on or off at any time. However, each time he turns on the stove, he consumes one match. JOI-kun only has $K$ matches, so he can only turn on the stove up to $K$ times. The stove is initially off at the beginning of the day.

Since the stove consumes fuel while it is on, JOI-kun wants to minimize the total time the stove is on by carefully determining when to turn it on and off.

Input Format

Read the following input from standard input:

• The first line contains two integers $N$ and $K$ separated by a space. This indicates that there will be $N$ guests visiting JOI-kun's room and JOI-kun has $K$ matches.
• The next $N$ lines contain an integer $T_i$ each. This indicates that the $i$-th guest arrives at time $T_i$ and leaves at time $T_i + 1$.

Output Format

Output the minimum total time the stove is on to standard output in one line.

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

Task

Given the information about the guests visiting JOI-kun's room and the number of matches JOI-kun has, find the minimum total time the stove is on.

Constraints

All input data satisfies the following conditions:

• $1 \leq N \leq 100,000$.
• $1 \leq K \leq N$.
• $1 \leq T_i \leq 1,000,000,000$ ($1 \leq i \leq N$).
• $T_i < T_{i+1}$ ($1 \leq i \leq N - 1$).

Subtasks

Subtask 1 [20 points]

Satisfies the following conditions:

• $N \leq 20$.
• $1 \leq T_i \leq 20$ ($1 \leq i \leq N$).

Subtask 2 [30 points]

• $N \leq 5,000$.

Subtask 3 [50 points]

• No additional constraints.

Sample Explanation 1

In this input example, there are $3$ guests visiting JOI-kun's room. If the stove is turned on and off as follows, the stove is on during the guests' visits, the number of times the stove is turned on is $2$, and the total time the stove is on is $(4 - 1) + (7 - 6) = 4$.

• Turn on the stove at time $1$ when the first guest arrives.
• Turn off the stove at time $4$ when the second guest leaves.
• Turn on the stove at time $6$ when the third guest arrives.
• Turn off the stove at time $7$ when the third guest leaves.

It is not possible to reduce the total time the stove is on to less than $4$, so the answer is $4$.

Sample Explanation 2

In this input example, JOI-kun can only turn on the stove once, so he should turn on the stove at time $1$ when the first guest arrives and turn it off at time $7$ when the third guest leaves. Note that the time a guest leaves may coincide with the time the next guest arrives.

Sample Explanation 3

In this input example, JOI-kun can turn on the stove each time a guest arrives and turn it off each time a guest leaves.

见题面 Input 部分

见题面 Output 部分