You have a long stick, consisting of $m$ segments enumerated from $1$ to $m$. Each segment is $1$ centimeter long. Sadly, some segments are broken and need to be repaired.

You have an infinitely long repair tape. You want to cut some pieces from the tape and use them to cover all of the broken segments. To be precise, a piece of tape of integer length $t$ placed at some position $s$ will cover segments $s, s+1, \ldots, s+t-1$.

You are allowed to cover non-broken segments; it is also possible that some pieces of tape will overlap.

Time is money, so you want to cut at most $k$ continuous pieces of tape to cover all the broken segments. What is the minimum total length of these pieces?


-----Input-----

The first line contains three integers $n$, $m$ and $k$ ($1 \le n \le 10^5$, $n \le m \le 10^9$, $1 \le k \le n$) — the number of broken segments, the length of the stick and the maximum number of pieces you can use.

The second line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le m$) — the positions of the broken segments. These integers are given in increasing order, that is, $b_1 < b_2 < \ldots < b_n$.


-----Output-----

Print the minimum total length of the pieces.


-----Examples-----
Input
4 100 2
20 30 75 80

Output
17

Input
5 100 3
1 2 4 60 87

Output
6



-----Note-----

In the first example, you can use a piece of length $11$ to cover the broken segments $20$ and $30$, and another piece of length $6$ to cover $75$ and $80$, for a total length of $17$.

In the second example, you can use a piece of length $4$ to cover broken segments $1$, $2$ and $4$, and two pieces of length $1$ to cover broken segments $60$ and $87$.

Difficulty: interview

Starter code:

Solutions:
n,m,k=map(int,input().split())
b=list(map(int,input().split()))
diffs=[]
for i in range(n-1):
    diffs.append(b[i+1]-b[i])
diffs.sort()
print(k+sum(diffs[:n-k]))

n, m, k = map(int, input().split())
b = list(map(int, input().split()))
c = []
for i in range(n-1):
	c.append(b[i+1] - b[i] - 1)
c = list(sorted(c))[::-1]
print(b[n-1] - b[0] + 1 - sum(c[:k-1]))

n,m,k = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort()
ans = a[n-1]-a[0]+1
k -= 1
b = []
for i in range(n-1):
    b.append(a[i+1]-a[i]-1)
b.sort(reverse = True)
ind = 0
k = min(k,len(b))
while k:
    ans -= b[ind]
    k -= 1
    ind += 1
print(ans)


from sys import setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

setrecursionlimit(10**7)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

n, m, k = reads()
b = reads()

df = [b[k+1] - b[k] - 1 for k in range(n-1)]
df.sort()
ans = n + sum(df[:n-k])
print(ans)

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
gal = A[-1] - A[0]
h = []
for z in range(1, n):
    h.append(A[z] - A[z - 1])
print(gal - sum(sorted(h, reverse=True)[:k-1]) + k)

n, m, k = map(int, input().split())
b = list(map(int, input().split()))
g = [b[i+1] - b[i] - 1 for i in range(n-1)]
g.sort(reverse=True)
ans = b[n-1] - b[0] + 1
for i in range(k-1):
	ans -= g[i]
print(ans)

ii = lambda: int(input())
mi = lambda: list(map(int, input().split()))
li = lambda: list(mi())

n, m, k = mi()
b = li()
if k >= n:
    ans = n
else:
    d = sorted((b[i + 1] - b[i], i) for i in range(n - 1))[::-1]
    s = {i for x, i in d[:k - 1]}
    ans = n
    for i in range(n - 1):
        if i not in s:
            ans += b[i + 1] - b[i] - 1
print(ans)


n,m,k=map(int,input().split())
b=[int(i) for i in input().split()]
if k==1:
    print(b[-1]-b[0]+1)
else:
    d=[b[i]-b[i-1] for i in range(1,n)]
    d.sort()
    d=d[:-k+1]
    print(sum(d)+k)


n, m, k = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

diffs = [b[i+1] - b[i] - 1 for i in range(len(b) - 1)]
diffs.sort()

print(n + sum(diffs[:n-k]))


n, m, k = list(map(int, input().split()))
b = list(map(int, input().split()))
b_dif = []
for i in range(n-1):
    b_dif.append(b[i+1]-b[i])
b_dif.sort()
ans = k
for i in range(n-k):
    ans += b_dif[i]
print(ans)


n, m, k = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
lis = []
for i in range(1,len(b)):
    lis.append(b[i]-b[i-1]-1)
lis.sort()
ans = n
for i in range(n-k):
    ans += lis[i]
print(ans)


(lambda N,M,K,n:print(N+sum(sorted(n[i+1]-n[i]-1for i in range(N-1))[:N-K])))(*map(int,input().split()),list(map(int,input().split())))

N,M,K = list(map(int,input().split()))
B = list(map(int,input().split()))

seq = 1
intervals = []
for a,b in zip(B,B[1:]):
    if b-a == 1: continue
    intervals.append(b-a-1)
    seq += 1

if seq <= K:
    print(N)
    return

intervals.sort()
ans = N + sum(intervals[:seq-K])
print(ans)


#n = int(input())
#n,m = map(int,input().split())
#a = list(map(int,input().split()))
n,m,k = map(int,input().split())
b = list(map(int,input().split()))
l = n
p = n
c = []
for i in range(n-1):
	c.append(b[i+1]-b[i]-1)
c = sorted(c)
for i in range(n-k):
	l+=c[i]
print(l)

n,m,k=map(int,input().split())
x=[*map(int,input().split())]
diff=[]
for i in range(n-1):
    diff.append([x[i+1]-x[i]-1,i])
diff.sort(reverse=True)

ori=x[-1]-x[0]+1
for i in range(k-1):
    ori-=diff[i][0]
print(ori)

n,m,k=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
delt=[]
for i in range(1,len(b)):
    a=b[i]-b[i-1]-1
    delt.append(a)
counter=b[-1]-b[0]+1
delt.sort(reverse=True)
for item in delt:
    if k<=1:
        break
    counter-=item
    k-=1
print(counter)


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

n, m, k = mints()
b = list(mints())
c = [0]*(n-1)
for i in range(1,len(b)):
	c[i-1] = b[i]-b[i-1]-1
c.sort()
r = n
for i in range(n-k):
	r += c[i]
print(r)

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
F = []
for i in range(1, n):
	F.append(A[i] - A[i - 1] - 1)
F.sort()
sum = 0
for i in range(0, n - k):
	sum += F[i]
print(sum + n)

3

import math
import sys


DEBUG = False


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, M, K, B):
    segs = []
    for i in range(N - 1):
        segs.append(B[i + 1] - B[i])

    segs.sort()
    ntapes = N
    tapelen = N
    j = 0
    while ntapes > K:
        tapelen += segs[j] - 1
        ntapes -= 1
        j += 1

    return tapelen


def main():
    N, M, K = [int(e) for e in inp().split()]
    B = [int(e) for e in inp().split()]
    print(solve(N, M, K, B))


def __starting_point():
    main()

__starting_point()

n,m,k = list(map(int, input().strip().split()))

b = list(map(int, input().strip().split()))

diffs = []

for j in range(len(b)-1):
    diffs.append(b[j+1] - b[j] - 1)

diffs.sort()

tape = len(b)

segmentov = len(b)
indeks = 0
while segmentov > k:
    tape += diffs[indeks]
    indeks += 1
    segmentov -= 1

print(tape)



n,m,k = list(map(int,input().split()))
bi = list(map(int,input().split()))
ai = [0] * (n-1)
for i in range(n-1):
    ai[i] = bi[i+1] - bi[i]
ai.sort()
num = n - k
ans = k
for i in range(num):
    ans += ai[i]
print(ans)



def main():
    n, m, k = [int(a) for a in input().split()]
    bis = [int(a) for a in input().split()]
    total_length = bis[-1] - bis[0]
    between = []
    for i in range(len(bis) - 1):
        between.append(bis[i+1] - bis[i])
    between.sort(reverse=True)
    for i in range(k-1):
        total_length -= between[i]
    total_length += k
    print(total_length)
main()


def get():
    return list(map(int,input().split()))
n,m,k=get()
a=get()
b=(n-1)*[0]
for i in range(1,n):
    b[i-1]=[a[i]-a[i-1],i]
d=[0]
b.sort(reverse=1)
for i in range(k-1):
    s=b.pop(0)
    d+=[s[1]]
d+=[n]
f=0
for i in range(1,len(d)):
    f+=a[d[i]-1]-a[d[i-1]]+1
print(f)


import sys
import math
input = sys.stdin.readline

n,m,k=map(int,input().split())

l=list(map(int,input().split()))

dist=[]

for i in range(n-1):
	dist.append(l[i+1]-l[i])

dist.sort()

ans=0
for i in range(n-k):
	ans+=dist[i]

ans+=k

print(ans)

n,m,k = list(map(int,input().split()));
b = list(map(int,input().split()));

print((b[n-1]-b[0]+1 - sum(sorted([b[i]-b[i-1]-1 for i in range(1,n)],reverse=True)[0:k-1])));