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$.

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Greedy algorithms


Solutions:
(n, m, k) = map(int, input().split())
b = list(map(int, input().split()))
c = [b[i + 1] - b[i] - 1 for i in range(n - 1)]
c.sort()
if k == n:
	ans = n
	print(ans)
	import sys
	sys.exit(0)
else:
	pass
ans = sum(c[:n - k]) + n
print(ans)


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


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


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5:
	from math import gcd
else:
	from fractions import gcd
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def ceil(a, b=1):
	return int(-(-a // b))

def round(x):
	return int((x * 2 + 1) // 2)

def fermat(x, y, MOD):
	return x * pow(y, MOD - 2, MOD) % MOD

def lcm(x, y):
	return x * y // gcd(x, y)

def lcm_list(nums):
	return reduce(lcm, nums, 1)

def gcd_list(nums):
	return reduce(gcd, nums, nums[0])

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
(N, M, K) = MAP()
B = LIST()
ans = M - (B[0] - 1) - (M - B[-1])
dist = [0] * (N - 1)
for i in range(N - 1):
	dist[i] = B[i + 1] - B[i] - 1
dist.sort(reverse=True)
for i in range(K - 1):
	if i == len(dist):
		break
	ans -= dist[i]
print(ans)


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


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


(n, m, k) = tuple(map(int, input().split()))
A = list(map(int, input().split()))
rasst = []
ans = n
for i in range(1, n):
	rasst.append((A[i] - A[i - 1] - 1, i))
rasst.sort(key=lambda x: -x[0])
for i in range(n - k):
	ans += rasst.pop()[0]
print(ans)


(n, m, k) = map(int, input().split())
mas = list(map(int, input().split()))
mas.sort()
raz = []
for i in range(1, n):
	raz.append(mas[i] - mas[i - 1] - 1)
raz.sort()
if k == 1:
	print(max(mas) - min(mas) + 1)
else:
	print(max(mas) - min(mas) + 1 - sum(raz[-(k - 1):]))


mod = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
(n, m, k) = f()
l = il()
ldif = []
for i in range(1, n):
	ldif.append(l[i] - l[i - 1])
ldif.sort()
print(sum(ldif[:n - k]) + k)


(n, m, k) = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [b[x] - b[x - 1] for x in range(1, len(b))]
c.sort()
now = n
i = 0
while n > k:
	n -= 1
	now += c[i] - 1
	i += 1
print(now)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(len(a) - 1):
	a[i] = a[i + 1] - a[i]
del a[n - 1]
a.sort()
s = 0
for i in range(n - k):
	s += a[i]
print(s + k)


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


import sys
read = lambda : map(int, sys.stdin.readline().split())
(n, m, k) = read()
b = list(read())
c = []
for i in range(1, n):
	c.append(b[i] - b[i - 1] + 1)
c.sort(reverse=True)
c = c[k - 1:]
print(sum(c) - len(c) + k)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
if n == k:
	print(k)
	exit(0)
d = []
ans = n
for i in range(n - 1):
	d.append(a[i + 1] - a[i] - 1)
d.sort()
r = n - k
for i in range(r):
	ans += d[i]
print(ans)


ll = lambda : list(map(int, input().split()))
[n, m, k] = ll()
brokenarr = ll()
diffarr = [brokenarr[i + 1] - brokenarr[i] for i in range(0, n - 1)]
diffarr.sort(reverse=True)
print(sum(diffarr[k - 1:]) + k)


(n, m, k) = 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) = map(int, input().split())
a = list(map(int, input().split()))
l = []
for i in range(1, n):
	l.append(a[i] - a[i - 1])
l.sort()
ans = k
for i in range(n - k):
	ans += l[i]
print(ans)


import sys
input = sys.stdin.readline
from heapq import heapify, heappop, heappush
from collections import Counter
(n, m, k) = map(int, input().split())
b = list(map(int, input().split()))
if k == n:
	print(n)
	sys.exit()
done = Counter()
segments = []
for i in range(n - 1):
	(f, s) = (b[i], b[i + 1])
	segments.append((s - f + 1, f, s))
segments.sort()
cost = 0
broken_segments = n
for (c, f, s) in segments:
	if done[f] and done[s]:
		cost += c - 2
		k += 1
	elif done[f] or done[s]:
		broken_segments -= 1
		cost += c - 1
		done[f] = 1
		done[s] = 1
	else:
		broken_segments -= 2
		cost += c
		k -= 1
		done[f] = 1
		done[s] = 1
	if broken_segments <= k:
		cost += broken_segments
		break
print(cost)


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


(a_n, length, tape_n) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
sub_a = sorted([a[i + 1] - a[i] for i in range(a_n - 1)])
if tape_n >= a_n:
	print(a_n)
	exit()
print(sum(sub_a[:a_n - 1 - tape_n + 1]) + tape_n)


(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) = map(int, input().split())
B = [int(i) for i in input().split()]
C = [(B[i] - B[i - 1], i - 1) for i in range(1, N)]
C = sorted(C, reverse=True)
L = [0] * (N - 1)
for i in range(K - 1):
	L[C[i][1]] = 1
t = B[0]
ans = 0
for i in range(1, N):
	if L[i - 1] == 1:
		ans += B[i - 1] - t + 1
		t = B[i]
if t != B[N - 1]:
	ans += B[N - 1] - t + 1
else:
	ans += 1
print(ans)


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


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
a += [a[-1] + 1]
edges = sorted([m - n for (i, (n, m)) in enumerate(zip(a, a[1:]))], reverse=True)
pop = edges.pop
ans = 0
for i in range(k - 1):
	edges[i] = 1
print(sum(edges))


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

def argsort(seq):
	return sorted(range(len(seq)), key=seq.__getitem__)
ind = argsort(cl)[::-1]
res = b[-1] - b[0]
for i in range(k - 1):
	res -= cl[ind[i]] - 1
print(res + 1)


l = [int(i) for i in input().split()]
n = l[0]
k = l[2]
b = [int(i) for i in input().split()]
gap = []
for i in range(1, n):
	gap.append(b[i] - b[i - 1])
gap.sort()
print('{}'.format(sum(gap[0:n - k:1]) + k))


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


(n, m, k) = map(int, input().split())
B = list(map(int, input().split()))
D = sorted((b1 - b0 - 1 for (b1, b0) in zip(B[1:], B)))
ans = n + sum(D[:max(0, n - k)])
print(ans)


import sys
import math

def getAndParseInt(num=1):
	string = sys.stdin.readline().strip()
	if num == 1:
		return int(string)
	else:
		return [int(part) for part in string.split()]

def getAndParseString(num=1, delim=' '):
	string = sys.stdin.readline().strip()
	if num == 1:
		return string
	else:
		return [part for part in string.split(delim)]
(n, m, k) = getAndParseInt(2)
broken = getAndParseInt(2)
diffs = []
for i in range(n - 1):
	diffs.append(broken[i + 1] - broken[i] - 1)
diffs.sort()
cur_length = broken[-1] - broken[0] + 1
cur_used = 1
for gap in reversed(diffs):
	if cur_used >= k:
		break
	cur_length = cur_length - gap
	cur_used += 1
print(cur_length)


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


list_int_input = lambda inp: list(map(int, inp.split()))
int_input = lambda inp: int(inp)
string_to_list_input = lambda inp: list(inp)
(n, m, k) = map(int, input().split())
b = list_int_input(input())
b = [b[i] - b[i - 1] for i in range(1, n)]
b.sort()
summ = k
for i in range(n - k):
	summ += b[i]
print(summ)


(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)


(n, m, k) = map(int, input().split())
l = list(map(int, input().split()))
l1 = []
for i in range(1, n):
	l1 += [l[i] - l[i - 1]]
l1.sort(reverse=True)
s = l[-1] - l[0] + 1
i = 0
while k > 1:
	s -= l1[i] - 1
	i += 1
	k -= 1
print(s)


(n, m, k) = map(int, input().split())
l = list(map(int, input().split()))
l1 = [l[i + 1] - l[i] for i in range(0, n - 1)]
l1.sort()
c = 0
for i in range(0, n - k):
	c = c + l1[i]
print(c + k)


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


(n, m, k) = list(map(int, input().split()))
a = list(map(int, input().rstrip().split()))
diff = []
for i in range(1, len(a)):
	diff.append(a[i] - a[i - 1])
if len(a) <= k:
	print(len(a))
	exit()
diff.sort()
sum1 = 0
for i in range(len(diff), -1, -1):
	if k > 1:
		sum1 += 1
	else:
		sum1 += sum(diff[0:i])
		break
	k -= 1
print(sum1 + 1)


(N, M, K) = 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)
	exit()
intervals.sort()
ans = N + sum(intervals[:seq - K])
print(ans)


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


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


a = input().split()
(n, m, k) = list(map(int, a))
a = list(map(int, input().split()))
h = []
for i in range(len(a) - 1):
	h.append(a[i + 1] - a[i])
h.sort()
ans = -100
if n <= k:
	ans = n
else:
	ans = n + sum(h[:n - k]) - (n - k)
print(ans)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
value = []
mark = [0 for _ in range(n)]
count = 0
tape = 0
if k >= n:
	print(n)
else:
	for i in range(n - 1):
		value.append([a[i + 1] - a[i] + 1, i, i + 1])
	value = sorted(value, key=lambda x: x[0])
	while n != k:
		next = value.pop(0)
		count += 1
		tape += next[0] - mark[next[2]] - mark[next[1]]
		mark[next[1]] = 1
		mark[next[2]] = 1
		n -= 1
	tape += mark.count(0)
	print(tape)


import sys

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline().strip('\n')
(n, m, k) = get_ints()
l = get_array()
diff = [0]
for i in range(1, n):
	diff.append(l[i] - l[i - 1] - 1)
diff.sort()
print(sum(diff[:n - k + 1]) + n)


(n, m, k) = tuple(map(lambda entry: int(entry), input().split()))
positions = list(map(lambda entry: int(entry), input().split()))
differences = []
for i in range(n - 1):
	difference = positions[i + 1] - positions[i] - 1
	differences.append(difference)
differences.sort(reverse=True)
if len(differences) < k:
	print(n)
else:
	ans = n
	ans += sum(differences[k - 1:])
	print(ans)


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


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


(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)


(n, m, k) = map(int, input().split())
l = [*map(int, input().split())]
l.sort()
d = [l[i] - l[i - 1] for i in range(1, n)]
d.sort(reverse=True)
res = k
while n > k:
	res += d.pop()
	n -= 1
print(res)


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

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

def myceil(x, y):
	return (x + y - 1) // y

def Solution(arr, n, m, k):
	if k == 1:
		print(arr[-1] - arr[0] + 1)
		return
	segs = []
	heap = []
	for i in range(n - 1):
		diff = arr[i + 1] - arr[i]
		if len(heap) == k - 1 and heap[0][0] < diff:
			heapq.heappop(heap)
			heapq.heappush(heap, (diff, i))
		elif len(heap) != k - 1:
			heapq.heappush(heap, (diff, i))
	while len(heap):
		segs.append(heapq.heappop(heap)[1])
	segs = sorted(segs)
	prev = 0
	ans = 0
	for i in range(len(segs)):
		ans += arr[segs[i]] - arr[prev] + 1
		prev = segs[i] + 1
	if segs[-1] != n - 1:
		ans += arr[-1] - arr[prev] + 1
	print(ans)

def main():
	(n, m, k) = get_ints_in_variables()
	arr = get_ints_in_list()
	Solution(arr, n, m, k)
main()


(n, m, k) = map(int, input().split())
c = list(map(int, input().split()))
l = k - 1
v = []
curr = c[0]
for i in range(1, n):
	v.append(c[i] - curr - 1)
	curr = c[i]
v.sort()
tot = n
for i in range(n - k):
	tot += v[i]
print(tot)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
i = 0
y = [0] * (n - 1)
while i < n - 1:
	y[i] = a[i + 1] - a[i]
	i += 1
y.sort()
res = p = n
j = n - k
if p == k:
	print(res)
else:
	i = 0
	while p > k:
		res += y[i] - 1
		i += 1
		p -= 1
	print(res)


import time
(m, n, k) = (int(i) for i in input().split())
b = [int(i) for i in input().split()]
start = time.time()
ans = m
if m > k:
	c = sorted([b[i + 1] - b[i] for i in range(m - 1)])
	ans += sum(c[:m - k]) + k - m
print(ans)
finish = time.time()


[n, m, k] = [int(i) for i in input().split()]
lst = [int(i) for i in input().split()]
totlen = lst[-1] - lst[0] + 1
diff = [lst[i + 1] - lst[i] for i in range(len(lst) - 1)]
diff.sort()
while not not diff and k > 1:
	torem = diff.pop()
	totlen = totlen - torem + 1
	k = k - 1
print(totlen)


import sys
(n, m, k) = map(int, input().split())
a = list(map(int, sys.stdin.readline().split()))
b = []
for j in range(1, n):
	b.append(a[j] - a[j - 1])
b.sort(reverse=True)
p = sum(b) - sum(b[:k - 1]) + k
print(p)


(n, m, k) = map(int, input().split())
difference = [0] * (n - 1)
a = list(map(int, input().split()))
for i in range(1, n):
	difference[i - 1] = a[i] - a[i - 1]
difference = sorted(difference)
summ = k
for val in difference[0:n - k]:
	summ += val
print(summ)


(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)


from sys import stdin, stdout
(n, m, k) = map(int, stdin.readline().split())
a = [int(x) for x in stdin.readline().split()]
total = n
b = []
for i in range(1, n, 1):
	b.append(a[i] - a[i - 1] + 1)
k = k - n
b.sort()
for element in b:
	if k >= 0:
		break
	k = k + 1
	total += element - 2
print(total)


(n, m, k) = map(int, input().split())
arr = [int(x) for x in input().split()]
diff = []
for i in range(1, n):
	adjacentDifference = arr[i] - arr[i - 1] + 1
	diff.append(adjacentDifference)
diff.sort()
totalTape = n
for i in range(n - k):
	calculation = diff[i] - 2
	totalTape += calculation
print(totalTape)


import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
rui = [0] * (n - 1)
for i in range(n - 1):
	rui[i] = a[i + 1] - a[i]
ans = a[-1] - a[0] + 1
rui.sort()
for i in range(k - 1):
	if rui:
		ans -= rui.pop()
		ans += 1
	else:
		print(n)
		exit()
print(ans)


(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)


(n, m, k) = map(int, input().split())
brkn = list(map(int, input().split()))
l = n - k
ans = n
if l > 0:
	brkngap = []
	for i in range(n - 1):
		brkngap.append(brkn[i + 1] - brkn[i])
	brkngap.sort()
	ans += sum(brkngap[:l]) - l
print(ans)


(n, m, k) = map(int, input().split())
l = list(map(int, input().split()))
temp = []
length = max(l) - min(l) + 1
for i in range(n - 1):
	temp.append(l[i + 1] - l[i])
temp.sort(reverse=True)
s = 0
for i in range(k - 1):
	s = s + temp[i] - 1
print(length - s)


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


(n, m, k) = [int(i) for i in input().split(' ')]
broklist = [int(i) for i in input().split(' ')]
S = 0
sumlist = [broklist[i + 1] - broklist[i] - 1 for i in range(broklist.__len__() - 1)]
sumlist.sort()
if k >= n:
	print(n)
else:
	for i in range(n - k):
		S += sumlist[i]
	print(S + n)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def YES(c):
	return IF(c, 'YES', 'NO')

def Yes(c):
	return IF(c, 'Yes', 'No')

def main():
	t = 1
	rr = []
	for _ in range(t):
		(n, m, k) = LI()
		a = LI()
		if n == 1:
			rr.append(1)
			continue
		t = []
		for i in range(1, n):
			t.append(a[i] - a[i - 1] - 1)
		t.sort(reverse=True)
		r = a[-1] - a[0] + 1 - sum(t[:k - 1])
		rr.append(r)
	return JA(rr, '\n')
print(main())


(n, m, k) = map(int, input().split())
B = list(map(int, input().split()))
if k >= n:
	print(k)
else:
	C = []
	for i in range(len(B) - 1):
		C.append(B[i + 1] - B[i])
	C = sorted(C)
	C = C[::-1]
	C = C[k - 1:]
	X = k + sum(C)
	print(X)


ls = list(map(int, input().split()))
ar = list(map(int, input().split()))
diff = list()
for i in range(0, len(ar) - 1):
	diff.append(ar[i + 1] - ar[i])
diff.sort()
print(int(ls[2]) + sum(diff[:int(ls[0]) - int(ls[2])]))


(n, m, k) = map(int, input().split())
ar1 = []
ar = [int(i) for i in input().split()]
for i in range(1, n):
	ar1.append(ar[i] - ar[i - 1] - 1)
rs = n
ar1.sort()
for i in range(n - k):
	rs += ar1[i]
print(rs)


(n, m, k) = map(int, input().split())
l = list(map(int, input().split()))
index = [[100000000000, 0]]
for j in range(1, n):
	diff = -l[j - 1] + l[j]
	index.append([diff, j])
index.sort(reverse=True)
index = index[:k]
(a, b) = map(list, zip(*index))
b.sort()
total = 0
for j in range(len(b)):
	if j != len(b) - 1:
		total += l[b[j + 1] - 1] - l[b[j]] + 1
	else:
		total += l[n - 1] - l[b[j]] + 1
print(total)


nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
a = input().split()
distances = []
for i in range(n - 1):
	distances.append(int(a[i + 1]) - int(a[i]))
k -= n
distances.sort(reverse=True)
i = len(distances)
while k < 0:
	i -= 1
	n += distances[i] - 1
	k += 1
print(n)


(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)


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


from math import *
(n, l, k) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
diff = []
for i in range(1, n):
	diff.append(a[i] - a[i - 1])
diff = sorted(diff)
i = len(diff) - 1
s = 1
while i >= 0 and s < k:
	s += 1
	i -= 1
print(sum(diff[:i + 1]) + k)


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


R = lambda : map(int, input().split())
(n, m, k) = R()
b = [*R()]
print(n + sum(sorted((y - x - 1 for (x, y) in zip(b, b[1:])))[:n - k]))


import heapq

def B():
	(n, m, k) = map(int, input().split())
	b = [int(x) for x in input().split()]
	dist = []
	for x in range(n - 1):
		heapq.heappush(dist, b[x + 1] - b[x] - 1)
	ans = n
	for i in range(n - k):
		ans += heapq.heappop(dist)
	print(ans)
B()


(n, m, k) = map(int, input().split())
segments = list(map(int, input().split()))
(i, d) = (0, [])
while i < len(segments) - 1:
	ln = segments[i + 1] - segments[i] - 1
	d.append(ln)
	i += 1
d.sort(reverse=True)
total = segments[-1] - segments[0] + 1
print(total - sum(d[:k - 1]))


import copy

def tape_problem():
	(n, m, k) = input().split(' ')
	(n, m, k) = (int(n), int(m), int(k))
	b = input().split(' ')
	b_t = [0]
	b_t.extend(b)
	b = b_t
	for (i, _) in enumerate(b):
		b[i] = int(b[i])
	c = copy.deepcopy(b)
	for i in range(1, n):
		c[i] = b[i + 1] - b[i] - 1
	c[-1] = 0
	c[1:] = sorted(c[1:], reverse=True)
	answer = b[n] - b[1] + 1
	for i in range(1, k):
		answer -= c[i]
	print(answer)
	return
tape_problem()


from collections import deque
import pdb
import heapq
from heapq import *
from pprint import pprint
from bisect import *
mod = 99999999999

def rI():
	return [int(i) for i in input().split()]
(n, m, k) = rI()
dat = rI()
rast = [() for i in range(n)]
sten = [False for i in range(n)] + [True]
for i in range(1, n):
	rast[i] = (dat[i] - dat[i - 1], i)
rast.sort()
rast.reverse()
for i in range(k - 1):
	(ln, pos) = rast[i]
	sten[pos] = True
out = 0
prev = 0
for i in range(n):
	if sten[i + 1] is True:
		out += dat[i] - dat[prev] + 1
		prev = i + 1
print(out)


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


nmk = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
li = []
if nmk[0] == nmk[2]:
	print(nmk[0])
elif nmk[2] == 1:
	print(b[-1] - b[0] + 1)
else:
	for i in range(nmk[0] - 1):
		li.append([b[i + 1] - b[i], i])
	li.sort(reverse=True)
	di = []
	for j in range(nmk[2] - 1):
		di.append(li[j][1])
	di.sort()
	low = 0
	up = 1
	l = 0
	res = b[di[0]] - b[0] + 1
	for k in range(1, nmk[2] - 1):
		res += b[di[up]] - b[di[low] + 1] + 1
		low += 1
		up += 1
	res += b[-1] - b[di[low] + 1] + 1
	print(res)


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


(n, m, k) = map(int, input().split())
b = [int(x) for x in input().split()]
c = [0]
for i in range(1, n):
	c.append(b[i] - b[i - 1] + 1)
ans = b[n - 1] - b[0] + 1
c.sort(reverse=True)
for i in range(k - 1):
	if c[i] == 0:
		break
	ans -= c[i] - 2
print(ans)


nmk = input().split(' ')
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
brokens = list(map(int, input().split(' ')))
if n == k:
	print(n)
else:
	distances = []
	for i in range(n - 1):
		distances.append(brokens[i + 1] - brokens[i] + 1)
	distances = sorted(distances)
	l = n
	j = 0
	used = n
	while used > k and j < n - 1:
		l += distances[j] - 2
		used -= 1
		j += 1
	print(l)


def f(k, a):
	arr = [el - a[i] for (i, el) in enumerate(a[1:])]
	arr.sort()
	total = a[-1] - a[0]
	if k == 1:
		return total + 1
	return total - sum(arr[-(k - 1):]) + k
here = [int(el) for el in input().split(' ')]
n = here[0]
m = here[1]
k = here[2]
a = [int(el) for el in input().split(' ')]
print(f(k, a))


import collections as cc
import sys
I = lambda : list(map(int, input().split()))
(n, m, k) = I()
l = I()
temp = []
for i in range(n - 1):
	temp.append(l[i + 1] - l[i])
temp.sort()
print(sum(temp[:n - k]) + k)


(n, m, k) = map(int, input().split())
arr = list(map(int, input().split()))
s = []
res = arr[len(arr) - 1] - arr[0] + 1
for i in range(len(arr) - 1):
	s.append(arr[i + 1] - arr[i])
s = sorted(s)
for i in range(k - 1):
	res -= s[n - i - 2] - 1
print(res)


a = input()
bb = input()
aa = a.split()
n = eval(aa[0])
m = eval(aa[1])
k = eval(aa[2])
b = bb.split()
for i in range(len(b)):
	b[i] = eval(b[i])
if k >= n:
	print(n)
else:
	x = n - k
	sub = []
	for i in range(len(b) - 1):
		sub.append(b[i + 1] - b[i])
	sub.sort()
	sum = 0
	for i in range(x):
		sum += sub[i]
	print(sum + k)


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


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
dis = []
for i in range(n - 1):
	dis.append(a[i + 1] - a[i])
dis.sort()
dis.reverse()
ans = n
while n > k:
	ans += dis[n - 2] - 1
	n -= 1
print(ans)


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


(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) = map(int, input().split())
l = list(map(int, input().split()))
diff = []
for i in range(1, n):
	diff.append(l[i] - l[i - 1])
diff.sort(reverse=True)
if k == n:
	print(k)
else:
	sum = 0
	for i in range(k - 1, len(diff)):
		sum += diff[i]
	print(sum + k)


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())
l = list(map(int, input().split()))
a = []
for i in range(1, n):
	a.append(l[i] - l[i - 1] - 1)
a.sort(reverse=True)
c = l[n - 1] - l[0] + 1
for i in range(k - 1):
	c -= a[i]
print(c)


from sys import stdin, stdout
from math import gcd, sqrt
from collections import deque
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
N = 10 ** 6 + 7
(n, m, k) = R()
a = L()
v = [1] * n
d = {}
if n > 1:
	for i in sorted([a[i] - a[i - 1] for i in range(1, n)])[:n - k]:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	if d:
		mn = max(d)
cnt = 0
val = n - k
for i in range(1, n):
	if cnt == val:
		break
	p = a[i] - a[i - 1]
	if p <= mn and d[p]:
		cnt += 1
		v += (a[i] - a[i - 1] + v[i - 1],)
		v[i] = v[i - 1] = 0
		d[p] -= 1
print(sum(v))


inp1 = str(input()).split(' ')
inp2 = str(input()).split(' ')
n = int(inp1[0])
m = int(inp1[1])
k = int(inp1[2])
a = [int(x) for x in inp2]
x = n - k
sum = 0
otr = []
for i in range(n - 1):
	otr.append(a[i + 1] - a[i])
otr.sort()
for i in range(x):
	sum += otr[i]
sum += k
print(sum)


from sys import stdin, stdout
from collections import defaultdict, Counter, deque
from bisect import bisect, bisect_left
import math
from itertools import permutations
import queue
I = stdin.readline
(n, m, k) = map(int, I().split())
arr = [int(x) for x in I().split()]
diff = []
tot = arr[-1] - arr[0] + 1
for i in range(1, n):
	diff.append(arr[i] - arr[i - 1] - 1)
diff.sort(reverse=True)
for i in range(min(n - 1, k - 1)):
	tot -= diff[i]
print(tot)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n - 1):
	b.append([a[i + 1] - a[i], i])
b.sort(reverse=True)
cnt = 1
c = [0] * n
ans = 0
for i in range(n - 1):
	if cnt < k:
		cnt += 1
		c[b[i][1]] = 1
x = a[0]
for i in range(n - 1):
	if c[i] == 1:
		ans += a[i] - x + 1
		x = a[i + 1]
ans += a[-1] - x + 1
print(ans)


(n, m, k) = map(int, input().split())
b = list(map(int, input().split()))
l = []
d = dict()
for i in range(n - 1):
	d[b[i]] = 1
	l.append((1 + b[i + 1] - b[i], b[i + 1], b[i]))
d[b[n - 1]] = 1
l.sort(reverse=True)
tn = n
cl = n
while tn > k:
	d[l[-1][1]] += 1
	d[l[-1][2]] += 1
	cl += l[-1][0]
	l.pop()
	tn -= 1
for i in d:
	cl -= d[i] - 1
print(cl)


import math
mod = 10 ** 9 + 7
(n, m, k) = map(int, input().split())
b = list(map(int, input().split()))
a = []
for i in range(1, n):
	a.append(b[i] - b[i - 1] - 1)
a.sort()
s = 0
for i in range(n - k):
	s += a[i]
print(s + n)


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)


t = list(map(int, input().split(' ')))
n = t[0]
m = t[1]
k = t[2]
b = list(map(int, input().split(' ')))
d = []
for i in range(1, n, 1):
	d.append(b[i] - b[i - 1])
d.sort(reverse=True)
s = sum(d[k - 1:]) + k
print(s)


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


(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)


(n, m, k) = [int(s) for s in input().split(' ')]
b = [int(s) for s in input().split(' ')]
l = min(k, n)
c = []
for i in range(n - 1):
	c.append((i, b[i + 1] - b[i]))
c.sort(key=lambda x: x[1], reverse=True)
c = c[:l - 1]
c.sort(key=lambda x: x[0])
c.append([n - 1, b[-1]])
c.insert(0, (-1, b[0]))
result = 0
for i in range(l):
	result += b[c[i + 1][0]] - b[c[i][0] + 1] + 1
print(result)


(n, m, k) = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
f = []
for j in range(1, n):
	f.append(t[j] - t[j - 1])
f.sort()
print(sum(f[:len(f) - (k - 1)]) + k)


(n, m, k) = map(int, input().split())
aa = list(map(int, input().split()))
if n == k:
	print(k)
	exit(0)
d = []
anss = n
for i in range(n - 1):
	d.append(aa[i + 1] - aa[i] - 1)
d.sort()
r = n - k
for i in range(r):
	anss += d[i]
print(anss)


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


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
if k == 1:
	print(a[-1] - a[0] + 1)
else:
	s = []
	for q in range(len(a) - 1):
		s.append(a[q + 1] - a[q])
	s.sort(reverse=True)
	d = s[k - 2]
	d1 = k - 2
	while d1 > -1 and s[d1] == s[k - 2]:
		d1 -= 1
	d1 += 1
	p = k - d1 - 1
	(answer, q2) = (0, a[0])
	for q in range(len(a) - 1):
		if a[q + 1] - a[q] > d:
			answer += a[q] - q2 + 1
			q2 = a[q + 1]
		elif a[q + 1] - a[q] == d and p > 0:
			p -= 1
			answer += a[q] - q2 + 1
			q2 = a[q + 1]
	answer += a[-1] - q2 + 1
	print(answer)


(n, m, k) = [int(s) for s in input().split()]
array = [int(s) for s in input().split()]
diffs = []
for i in range(len(array) - 1):
	diffs.append(array[i + 1] - array[i])
sorted_array = sorted(diffs)
ans = sum(sorted_array[:len(sorted_array) - k + 1])
print(ans + k)


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


(n, m, k) = map(int, input().split())
l1 = list(map(int, input().split()))
ans = n
if k >= n:
	print(ans)
else:
	l2 = []
	for i in range(len(l1) - 1):
		a = l1[i + 1] - l1[i]
		l2.append(a)
	l2.sort()
	for i in range(n - k):
		ans += l2[i] - 1
	print(ans)


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


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


from heapq import nlargest
(n, m, k) = map(int, input().split())
arr = sorted(list(map(int, input().split())))
diff = []
for i in range(1, n):
	diff.append(arr[i] - arr[i - 1])
print(arr[-1] - arr[0] - sum(nlargest(k - 1, diff)) + k)


(n, m, k) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
segments = []
for i in range(1, n):
	segments.append(a[i] - a[i - 1])
segments.sort()
length = sum(segments[:n - k]) + k
print(length)


(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) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
l1 = []
for i in range(len(arr) - 1):
	l1.append(arr[i + 1] - arr[i])
l1.sort()
ans = 0
ans += sum(l1[:n - k]) + k
print(ans)


(a, b, c) = map(int, input().split())
d = [*map(int, input().split())]
dis = [d[i + 1] - d[i] for i in range(a - 1)]
dis.sort()
print(c + sum(dis[:a - c]))


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


import time, random
nums1 = list(map(int, input().split()))
n = nums1[0]
m = nums1[1]
k = nums1[2]
broke = list(map(int, input().split()))
dists = []
for i in range(len(broke)):
	if i >= len(broke) - 1:
		break
	dists.append(broke[i + 1] - broke[i])
dists.sort()
sum = n
x = n - k
if n <= k:
	print(sum)
else:
	j = 0
	for i in range(x):
		sum += dists[j] - 1
		j += 1
	print(sum)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
from bisect import *
from math import floor, sqrt, ceil, factorial as F, gcd, pi, log
from itertools import chain, combinations, permutations, accumulate
from collections import Counter, defaultdict, OrderedDict, deque
from functools import cmp_to_key, reduce
INT_MAX = sys.maxsize
INT_MIN = -sys.maxsize - 1
mod = 1000000007
ch = 'abcdefghijklmnopqrstuvwxyz'
lcm = lambda a, b: a * b // gcd(a, b)
setbit = lambda x: bin(x)[2:].count('1')
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def solve():
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	diff = []
	for i in range(1, n):
		diff.append(a[i] - a[i - 1])
	diff.sort()
	print(sum(diff[:n - k]) + k)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
solve()


(n, m, k) = map(int, input().split(' '))
stick = list(map(int, input().split(' ')))
diff = []
for i in range(0, len(stick) - 1):
	diff.append(stick[i + 1] - stick[i] - 1)
length = stick[-1] - stick[0] + 1
diff.sort()
diff = diff[::-1]
for i in range(0, k - 1):
	length -= diff[i]
print(length)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m, k) = list(map(int, input().split()))
b = list(map(int, input().split()))
s = sorted([b[i] - b[i - 1] - 1 for i in range(1, n)], reverse=True)
mv = b[-1] - b[0] + 1 - sum(s[:k - 1])
print(mv)


R = lambda : map(int, input().split())
(n, m, k) = R()
b = [*R()]
dist = sorted([b[i + 1] - b[i] for i in range(0, n - 1)])
print(sum(dist[:n - k]) + k)


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


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


from collections import defaultdict, Counter
from bisect import bisect, bisect_left

def read():
	return list(map(int, input().strip().split()))
ans_ = []
(n, m, k) = read()
arr = read()
tot = arr[-1] - arr[0] + 1
arr = [arr[i] - arr[i - 1] - 1 for i in range(1, n)]
arr.sort()
ans = tot
for i in range(k - 1):
	tot -= arr.pop()
	ans = min(ans, tot)
print(ans)


s = input()
s = s.split()
n = int(s[0])
m = int(s[1])
k = int(s[2])
s = input()
s = s.split()
b = [int(s[0])]
db = []
for i in range(1, n):
	b.append(int(s[i]))
	db.append(b[i] - b[i - 1])
r = sorted(db)
ans = n
for i in range(n - k):
	ans += r[i] - 1
print(ans)


(n, m, k) = map(int, input().split())
b = [int(x) for x in input().split()]
a = []
for i in range(len(b) - 1):
	a.append(b[i + 1] - b[i] + 1)
diff = n - k
a.sort()
sm = n
for i in range(diff):
	sm += a[i] - 2
print(sm)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
t = 0
if k == 1:
	t = a[n - 1] - a[0] + 1
elif k >= n:
	t = n
else:
	x = n - k
	t = k - x
	c = [0] * (n - 1)
	for i in range(1, n):
		c[i - 1] = a[i] - a[i - 1] + 1
	c = sorted(c)
	for i in range(x):
		t += c[i]
print(t)


(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(reverse=True)
sol = n
num = n
j = 1
while num > k:
	if dist:
		sol += dist.pop() - 1
	num -= 1
print(sol)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (len(a) - 1)
for i in range(len(a) - 1):
	b[i] = a[i + 1] - a[i] - 1
if len(a) > k:
	b.sort(reverse=True)
	print(sum(b[k - 1:]) + len(a))
else:
	print(len(a))


def tape(sum, arr, n, k):
	b = len(d)
	if k > b:
		return sum
	else:
		for i in range(b + 1 - k):
			sum += arr[i]
		return sum
(n, m, k) = map(int, input().split())
(b, c) = ([], [])
b += map(int, input().split())
i = 1
while i < n:
	c.append(b[i] - b[i - 1] - 1)
	i += 1
d = []
for i in range(n - 1):
	if c[i] > 0:
		d.append(c[i])
d.sort()
sum = n
ans = tape(sum, d, n, k)
print(ans)


(n, m, k) = map(int, input().split())
p = [int(x) for x in input().split()]
if k == n:
	print(n)
else:
	t = n - k
	q = [0] * (n - 1)
	for i in range(0, n - 1):
		q[i] = p[i + 1] - p[i]
	q = sorted(q)
	s = 0
	for i in range(0, t):
		s += q[i] - 1
	print(s + n)


p = []
(n, m, k) = map(int, input().split())
a = [int(z) for z in input().split()]
for i in range(n - 1):
	p.append(a[i + 1] - a[i] - 1)
p.sort()
p.reverse()
print(n + sum(p) - sum(p[:k - 1]))


from sys import stdin, stdout

def inp():
	return int(stdin.readline())

def minp():
	return map(int, stdin.readline().rstrip().split())

def linp():
	return list(minp())

def main():
	(n, m, k) = minp()
	l = linp()
	s = 0
	a = []
	for i in range(1, n):
		a.append(l[i] - l[i - 1])
	a.sort()
	for i in range(n - k):
		s += a[i]
	print(s + k)
main()


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


from sys import *
from math import *
(n, m, k) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
d = []
for i in range(1, n):
	d.append(a[i] - a[i - 1])
d.sort()
print(sum(d[:len(d) - (k - 1)]) + k)


(n, m, k) = map(int, input().split())
s = list(map(int, input().split()))
sl = [s[i + 1] - s[i] for i in range(n - 1)]
sl.sort()
M = n - k
ans = n
for x in sl[:M]:
	ans += x - 1
print(ans)


import sys
(n, m, k) = [int(tmp) for tmp in sys.stdin.readline().split()]
b = [int(tmp) for tmp in sys.stdin.readline().split()]
ll = b[n - 1] - b[0] + 1
p = 1
if p < n and p < k:
	ls = []
	lb = b[0]
	for br in b:
		cs = br - lb - 1
		if cs > 0:
			ls.append(cs)
		lb = br
	ls.sort(reverse=True)
	lenls = len(ls)
	for s in ls:
		if p > lenls or p == k:
			break
		ll -= s
		p += 1
print(ll)


(n, m, k) = map(int, input().split())
B = [int(a) for a in input().split()]
A = [B[i + 1] - B[i] for i in range(n - 1)]
A = sorted(A)
print(sum(A[:n - k]) + min(k, n))


nmk = input().split(' ')
(n, m, k) = (int(nmk[0]), int(nmk[1]), int(nmk[2]))
b = list(map(int, input().split(' ')))
d = []
for i in range(1, n):
	d.append(b[i] - b[i - 1])
d.sort()
temp = n
for i in range(n - k):
	temp += d[i] - 1
print(temp)


(n, m, k) = map(int, input().split())
x = list(map(int, input().split()))
x1 = []
for i in range(n - 1):
	x1.append(x[i + 1] - x[i] - 1)
x1.sort()
i = n - 2
s = 0
while True:
	if k == 1:
		break
	x[n - 1] -= x1[i]
	k = k - 1
	i -= 1
print(x[n - 1] - x[0] + 1)


from sys import stdin
max_val = int(10000000000000.0)
min_val = int(-10000000000000.0)

def read_int():
	return int(stdin.readline())

def read_ints():
	return [int(x) for x in stdin.readline().split()]

def read_str():
	return input()

def read_strs():
	return [x for x in stdin.readline().split()]
(n, m, k) = read_ints()
arr = read_ints()
gaps = sorted([y - x - 1 for (x, y) in zip(arr, arr[1:])])
ans = arr[-1] - arr[0] + 1 - sum(gaps[n - k:])
print(ans)


(n, m, k) = map(int, input().split())
b = list(map(int, input().split()))
gaps = []
for i in range(1, n):
	gap = b[i] - b[i - 1]
	gaps.append(gap)
gaps.sort()
sumgaps = 0
i = n - 2
while i > n - k - 1 and i > -1:
	sumgaps += gaps[i]
	i -= 1
print(b[n - 1] - b[0] - sumgaps + k)


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


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


(n, m, k) = map(int, input().split())
ls = list(map(int, input().split()))
ans = ls[n - 1] - ls[0]
ls1 = []
for i in range(1, n):
	ls1.append(ls[i] - ls[i - 1])
ls1.sort()
count = 0
if k != 1:
	for x in reversed(ls1):
		ans = ans - x
		count = count + 1
		if count == k - 1:
			break
ans = ans + k
print(ans)


import math
(m, n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(list(map(lambda x, y: abs(x - y), a[0:-1], a[1:])))
print(k + sum(b[0:m - k]))


(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)


(n, m, k) = map(int, input().split())
arr = list(map(int, input().split()))
diff = []
for i in range(1, n):
	diff.append(arr[i] - arr[i - 1])
diff.sort(reverse=True)
ans = arr[-1] - arr[0] + 1
i = 0
segments = 1
while segments < k:
	ans -= diff[i]
	ans += 1
	i += 1
	segments += 1
print(ans)


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()


import sys, math, bisect
from random import randint
inf = float('inf')
mod = 10 ** 9 + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def tobinary(n):
	return bin(n)[2:]

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def primesInRange(n):
	ans = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def primeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n // i
	if n > 2:
		factors.append(n)
	return factors

def isPrime(n, k=5):
	if n < 2:
		return True
	for i in range(0, k):
		a = randint(1, n - 1)
		if pow(a, n - 1, n) != 1:
			return False
	return True
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import string
(n, m, k) = map(int, input().split())
arr = list(map(int, input().split()))
c = []
for i in range(1, n):
	c.append(arr[i] - arr[i - 1] - 1)
c.sort()
print(n + sum(c[:n - k]))


def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))
(n, m, k) = mi()
blist = lm()
dif = [blist[i + 1] - blist[i] for i in range(n - 1)]
dif.sort()
total = 0
for i in range(n - k):
	total = total + dif[i]
total = total + k
print(total)


(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)


def Funcion(arreglo, n, m, k):
	suma = 0
	separaciones = []
	for i in range(len(arreglo) - 1):
		separaciones.append(arreglo[i + 1] - arreglo[i])
	separaciones_s = sorted(separaciones)
	for i in range(n - k):
		diff = separaciones_s[i]
		suma = suma + diff
	return suma + k
(n, m, k) = list(map(int, input().split()))
arreglo = list(map(int, input().split()))
print(Funcion(arreglo, n, m, k))


(n, m, k) = list(map(int, input().split()))
segs = list(map(int, input().split()))
gaps = []
for i in range(1, len(segs)):
	gaps.append(segs[i] - segs[i - 1])
gaps.sort(reverse=True)
answer = segs[len(segs) - 1] - segs[0]
for i in range(min(k - 1, len(gaps))):
	answer -= gaps[i]
print(answer + k)


(n, m, k) = list(map(int, input().split()))
lst = list(map(int, input().split()))
val = sorted([y - x for (x, y) in zip(lst[:-1], lst[1:])], reverse=True)
print(sum(val) - sum(val[:k - 1]) + k)


(n, l, s) = list(map(int, input().split()))
a = list(map(int, input().split()))
res = []
for i in range(n - 1):
	res.append([a[i + 1] - a[i], i])
res.sort()
if s == 1:
	su = a[-1] - a[0] + 1
else:
	res = res[-s + 1:]
	res.reverse()
	su = a[-1] - a[0] + 1
	for i in range(len(res)):
		su -= a[res[i][1] + 1] - a[res[i][1]] - 1
print(su)


(n, m, k) = map(int, input().split())
pos = list(map(int, input().split()))
ans = n
if n > 1:
	a = [pos[1] - pos[0] - 1]
	for i in range(2, n):
		a.append(pos[i] - pos[i - 1] - 1)
	a.sort()
	n -= k
	while n > 0:
		ans += a.pop(0)
		n -= 1
print(ans)


(n, m, k) = [int(x) for x in input().split()]
L = [int(x) for x in input().split()]
L.append(2 * L[-1])
t = n
i = 1
Q = []
while i < n:
	Q.append(L[i] - L[i - 1])
	i += 1
Q.sort()
for i in range(max(0, len(Q) - k + 1)):
	t += Q[i] - 1
print(t)


(n, m, k) = [int(i) for i in input().split()]
s = [int(i) for i in input().split()]
e = sorted([s[i] - s[i - 1] - 1 for i in range(1, n)])
if k == 1:
	print(sum(e) + n)
elif k == n:
	print(k)
else:
	print(sum(e[:-k + 1]) + n)


(n, m, k) = map(int, input().strip().split())
l = list(map(int, input().strip().split()))
for i in range(n - 1):
	l[i] = l[i + 1] - l[i]
l.sort()
sums = 0
for i in range(n - k):
	sums += l[i]
print(sums + k)


def inint():
	return int(input())

def mp():
	return map(int, input().split())
(n, m, k) = mp()
b = list(mp())
if n == k:
	print(n)
	exit()
a = sorted(([b[i + 1] - b[i] - 1, i] for i in range(n - 1)))
a = a[::-1]
ans = b[-1] - b[0] + 1
for i in range(k - 1):
	ans -= a[i][0]
print(ans)


(n, l, p) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
q = []
for i in range(n - 1):
	q.append(a[i + 1] - a[i])
q.sort()
if p == n:
	print(p)
else:
	z = n - p
	q = q[:z]
	print(sum(q) + p)


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


(n, m, k) = map(int, input().split())
arr = list(map(int, input().split()))
l = arr[-1] - arr[0] + 1
diffs = []
for i in range(len(arr) - 1):
	diffs.append([arr[i + 1] - arr[i], (i, i + 1)])
diffs.sort(key=lambda x: x[0], reverse=True)
for x in range(k - 1):
	if x == len(diffs):
		break
	l -= diffs[x][0] - 1
print(l)


(n, m, k) = (int(i) for i in input().split())
l = [int(i) for i in input().split()]
l1 = []
for i in range(n - 1):
	l1 += [l[i + 1] - l[i]]
l1.sort()
print(sum(l1[:n - k]) + k)


def chPathToThis(f=None):
	import os
	f = __file__ if f is None else f
	os.chdir(os.path.dirname(f))
fle = None

def input():
	global fle

	def inner():
		if fle is None:
			from sys import stdin
			for line in stdin:
				yield line
			raise EOFError
		else:
			for line in fle:
				yield line.replace('\r', '').replace('\n', '')
			raise EOFError
	o = inner()
	return next(o)

def main():
	(n, m, k) = map(int, input().split())
	(b, v) = ([int(e) for e in input().split()], [])
	ans = b[n - 1] - b[0] + 1
	for i in range(n - 1):
		v.append(b[i + 1] - b[i] - 1)
	v.sort(reverse=True)
	for i in range(k - 1):
		ans -= v[i]
	print(ans)
try:
	import time, numpy
	chPathToThis(__file__)
	(begin, fle) = (time.clock(), open('pytest.txt'))
	main()
	fle.close()
	print(time.clock() - begin)
except ImportError:
	main()


(n, m, k) = list(map(int, input().split()))
array = list(map(int, input().split()))
check_sum = array[-1] - array[0] + 1
diff = [j - i - 1 for (i, j) in zip(array[:-1], array[1:])]
diff.sort(reverse=True)
print(check_sum - sum(diff[:k - 1]))


(x, y, z) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(0, x - 1):
	b.append(a[i + 1] - a[i])
b = sorted(b)[::-1]
s = sum(b[z - 1:])
print(s + z)


import sys

def fastio():
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
(n, m, k) = I()
a = I()
if k >= n:
	print(n)
	exit()
b = []
for i in range(1, n):
	b.append(a[i] - a[i - 1])
b.sort()
print(k + sum(b[:n - k]))


l = input().split()
n = int(l[0])
m = int(l[1])
k = int(l[2])
l = input().split()
li = [int(i) for i in l]
z = li[-1] - li[0]
l = []
for i in range(1, n):
	l.append(li[i] - li[i - 1])
l.sort()
l.reverse()
for i in range(k - 1):
	z = z - l[i]
print(z + k)


(n, m, k) = [int(t) for t in input().split(' ')]
b = [int(t) for t in input().split(' ')]
general = n // k
rest = n % k
INF = 2 * m + 1
delta = [None] * n
for i in range(n):
	delta[i] = (i, b[i] - b[i - 1] if i > 0 else INF)
delta.sort(reverse=True, key=lambda x: x[1])
starts = [t[0] for t in delta][:k]
starts.sort()
starts.append(n)
length = 0
for i in range(k):
	start = starts[i]
	end = starts[i + 1]
	total = b[end - 1] - b[start] + 1
	length += total
print(length)


class Range:

	def __init__(self, start, end):
		self.start = start
		self.end = end

	@property
	def length(self):
		return self.end - self.start + 1

	def join(self, rhs):
		self.end = rhs.end
(n, m, k) = tuple(map(int, input().split(' ')))
b = tuple(map(int, input().split(' ')))
if k >= m:
	print(m)
else:
	range_diffs = [0] * (n - 1)
	for i in range(n - 1):
		range_diffs[i] = b[i + 1] - b[i] + 1
	range_diffs.sort()
	length = n
	for i in range(n - k):
		length += range_diffs[i] - 2
	print(length)


import math as mt
import sys, string
from collections import Counter, defaultdict
input = sys.stdin.readline
MOD = 1000000007
PI = 3.141592653589793
I = lambda : int(input())
S = lambda : input()
M = lambda : map(int, input().split())
Ms = lambda : map(str, input().split())
ARR = lambda : list(map(int, input().split()))

def solve():
	(n, m, k) = M()
	ar = ARR()
	diff = [ar[i] - ar[i - 1] + 1 for i in range(1, n)]
	if len(diff) == 0:
		print(1)
		return
	diff.sort()
	ans = 0
	for i in range(n - k):
		ans += diff[i]
	ans += n - 2 * (n - k)
	print(ans)
tc = 1
for _ in range(tc):
	solve()


def mp():
	return map(int, input().split())
(n, m, k) = mp()
b = list(mp())
a = [0] * (n - 1)
for i in range(n - 1):
	a[i] = b[i + 1] - b[i]
a.sort(reverse=True)
ans = b[-1] - b[0] + 1
for i in range(k - 1):
	ans -= a[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) = map(int, input().split())
pos = list(map(int, input().split()))
ans = pos[n - 1] + 1 - pos[0]
diffs = []
for i in range(1, n):
	diffs.append(pos[i] - pos[i - 1] - 1)
diffs.sort()
diffs.reverse()
for i in range(k - 1):
	ans -= diffs[i]
print(ans)


(n, m, k) = map(int, input().split())
b = list(map(int, input().split()))
lis = [[0] * 2 for i in range(n)]
k -= 1
ans = 0
for i in range(1, n):
	lis[i][0] = b[i] - b[i - 1]
	lis[i][1] = i
lis.sort()
li = lis[n - k:]
li = [[0, 0]] + sorted(li, key=lambda x: x[1]) + [[0, n]]
for i in range(1, len(li)):
	a = li[i][1]
	z = li[i - 1][1]
	ans += b[a - 1] - b[z] + 1
print(ans)


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


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


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
sys.setrecursionlimit(int(pow(10, 6)))
mod = int(pow(10, 9) + 7)
mod2 = 998244353

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

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
for _ in range(1):
	(n, m, k) = l()
	b = l()
	d = []
	for i in range(1, n):
		d.append(b[i] - b[i - 1])
	d.sort()
	print(sum(d[:n - k]) + k)


import copy
import fractions
import itertools
import numbers
import string
import sys

def to_basex(num, x):
	while num > 0:
		yield (num % x)
		num //= x

def from_basex(it, x):
	ret = 0
	p = 1
	for d in it:
		ret += d * p
		p *= x
	return ret

def core():
	(n, m, k) = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	deltas = [y - x for (x, y) in zip(b[:-1], b[1:])]
	deltas.sort()
	ans = k
	ans += sum(deltas[:len(deltas) + 1 - k])
	print(ans)
core()


nk = list(map(int, input().split()))
(n, m, k) = (nk[0], nk[1], nk[2])
gaps = []
b = list(map(int, input().split()))
for i in range(n):
	if i != 0:
		gaps.append(b[i] - b[i - 1])
gaps.sort(reverse=True)
answer = b[-1] - b[0]
for i in range(min(k - 1, len(gaps))):
	answer -= gaps[i]
print(answer + k)


(x, m, k) = map(int, input().split())
s = [int(n) for n in input().split()]
if x != 1:
	for n in range(x - 1):
		s[n] = s[n + 1] - s[n]
	l = 0
	s.sort()
	for n in range(len(s) - k):
		l += s[n]
	print(l + k)
else:
	print(k)


(n, m, k) = map(int, input().split())
ll = list(map(int, input().split()))
ll = [0] + ll
for i in range(1, n):
	ll[i] = ll[i + 1] - ll[i]
ll = sorted(ll)
ans = n
for i in range(1, n - k + 1):
	ans += ll[i] - 1
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()


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


from sys import stdin, exit
(n, m, k) = map(int, input().split())
b = list(map(int, stdin.readline().strip().split()))
if k >= n:
	print(n)
	exit(0)
else:
	interval = sorted((b[i + 1] - b[i] - 1 for i in range(n - 1)))
	print(n + sum(interval[:n - k]))


(n, m, k) = map(int, input().split())
length = n
a = [int(i) for i in input().split()]
d = []
for j in range(n - 1):
	d.append(a[j + 1] - a[j] - 1)
d.sort()
for j in range(n - k):
	length += d[j]
print(length)


(_, maxlen, k) = input().split()
k = int(k)
dashes = input().split()
for i in range(len(dashes)):
	dashes[i] = int(dashes[i])
gaps = []
for i in range(1, len(dashes)):
	gaps.append(dashes[i] - dashes[i - 1])
gaps.sort()
for i in range(0, k - 1):
	gaps.pop()
print(sum(gaps) + k)


import heapq
(n, m, k) = map(int, input().split())
lst = list(map(int, input().split()))
ned = n - k
cur = []
for i in range(1, n):
	cur.append(lst[i] - lst[i - 1])
cur.sort()
print(sum(cur[:ned]) + k)


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)


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) = [int(s) for s in input().split(' ')]
pos = [int(s) for s in input().split(' ')]
segments = []
need = n - k
for i in range(n - 1):
	segment = pos[i + 1] - pos[i]
	if segment == 1:
		need -= 1
	else:
		segments.append(segment - 1)
segments = sorted(segments)
if need <= 0:
	print(n)
else:
	print(n + sum(segments[:need]))


(n, m, k) = map(int, input().split())
b = list(map(int, input().split()))
l = b[-1] - b[0] + 1
df = []
for i in range(1, n):
	df.append((b[i] - b[i - 1], b[i - 1], b[i]))
df = sorted(df, key=lambda x: x[0])
for i in range(k - 1):
	rng = df.pop()
	l -= rng[0] - 1
print(l)


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


import sys, itertools, math, collections, random

def ia():
	return [int(i) for i in sys.stdin.readline().strip().split(' ')]

def ii():
	return int(sys.stdin.readline().strip())

def istr():
	return sys.stdin.readline().strip()
(n, m, k) = ia()
B = ia()
G = []
l = B[0]
for b in B[1:]:
	g = b - l - 1
	l = b
	G.append(g)
G = sorted(G)
ans = n
for i in range(n - k):
	ans += G[i]
print(ans)


(n_num, m_num, k_num) = map(int, input().split(' '))
b_list = list(map(int, input().split(' ')))
b_space = {}
for i in range(n_num - 1):
	b_space[i] = b_list[i + 1] - b_list[i]
sort_b_scape = {}
for (k, v) in sorted(b_space.items(), key=lambda x: -x[1]):
	sort_b_scape[k] = v
cut_list = []
if 1 < k_num:
	cut_list = list(sort_b_scape)[:k_num - 1]
cut_list.sort()
repair_len = 0
prev = 0
for b_pos in cut_list:
	cut_gp = b_list[prev:b_pos + 1]
	repair_len += cut_gp[len(cut_gp) - 1] - cut_gp[0] + 1
	prev = b_pos + 1
cut_gp = b_list[prev:]
repair_len += cut_gp[len(cut_gp) - 1] - cut_gp[0] + 1
print(repair_len)


(n, m, k) = map(int, input().split())
b = list(map(int, input().split()))
distances = []
start = 0
end = 1
while end < len(b):
	distances.append(b[end] - b[start])
	start += 1
	end += 1
mine = len(distances) - k + 1
distances = sorted(distances)
solo = len(distances) - mine
print(sum(distances[:mine]) + solo + (k - solo))


l = [int(y) for y in input().split()]
a = [int(y) for y in input().split()]
temp = []
for key in range(1, len(a)):
	temp.append(a[key] - a[key - 1])
temp = sorted(temp, reverse=True)
pk = a[len(a) - 1] - a[0] + l[2]
b = sum(temp[:l[2] - 1])
print(pk - b)


(n, m, k) = map(int, input().split())
a = sorted(list(map(int, input().split())))
sumi = len(a)
ans = []
for i in range(0, len(a) - 1):
	ans.append(a[i + 1] - a[i] - 1)
ans.sort()
if k == n:
	print(sumi)
else:
	k = n - k
	i = 0
	while k > 0:
		sumi += ans[i]
		k -= 1
		i += 1
	print(sumi)


from sys import stdin
(n, m, k) = map(int, stdin.readline().strip().split())
s = list(map(int, stdin.readline().strip().split()))
ans = s[-1] - s[0] + 1
s1 = []
for i in range(1, n):
	s1.append(s[i] - s[i - 1] - 1)
s1.sort()
for i in range(len(s1) - k + 1, len(s1)):
	ans -= s1[i]
print(ans)


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


(n, m, k) = (int(x) for x in input().split())
b = [int(x) for x in input().split()]
deltaB = sorted([b[i + 1] - b[i] for i in range(n - 1)])
print(sum(deltaB[:n - k]) + k)


(n, m, w) = map(int, input().split())
l = list(map(int, input().split()))
k = []
for i in range(1, n):
	a = l[i] - l[i - 1]
	k.append(a)
k.sort()
s = 0
for i in range(n - w):
	s += k[i]
print(s + w)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
d = []
for i in range(n - 1):
	d.append(a[i + 1] - a[i] - 1)
d.sort(reverse=True)
if n > k:
	print(len(a) + sum(d[k - 1:]))
else:
	print(len(a))


t = [int(j) for j in input().split()]
(N, L, P) = (t[0], t[1], t[2])
inp = [int(j) for j in input().split()]
lis = []
for i in range(0, N - 1):
	lis.append(abs(inp[i] - inp[i + 1]))
lis = sorted(lis)
m = N - P
su = 0
for k in range(m):
	su = su + lis[0]
	lis.pop(0)
print(su + len(lis) + 1)


from sys import stdin, stdout
input = stdin.readline
listin = lambda : list(map(int, input().split()))
mapin = lambda : map(int, input().split())
(n, m, k) = mapin()
a = listin()
b = []
for i in range(1, n):
	b.append(a[i] - a[i - 1])
b.sort()
ans = n
i = 0
while n > k:
	ans += b[i] - 1
	i += 1
	n -= 1
print(ans)


import sys, os, io

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

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions
from collections import deque, defaultdict, OrderedDict
from fractions import Fraction
from decimal import Decimal

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	for i in range(1):
		(n, m, k) = ria()
		b = ria()
		d = []
		ans = n
		for i in range(n - 1):
			d.append(b[i + 1] - b[i])
		d = sorted(d)
		z = n
		for i in range(n - 1):
			if z == k:
				break
			ans += d[i] - 1
			z -= 1
		print(ans)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


entrada = input().split(' ')
n = int(entrada[0])
m = int(entrada[1])
k = int(entrada[2])
broken_segment = input().split(' ')
segment_distance = []
for i in range(n):
	if i > 0:
		temp = int(broken_segment[i]) - int(broken_segment[i - 1])
		segment_distance.append(temp)
min_tape = int(broken_segment[n - 1]) - int(broken_segment[0]) + 1
ans = 1
i = len(segment_distance) - 1
segment_distance.sort()
for j in range(k - 1):
	temp = segment_distance[i]
	if temp:
		min_tape -= temp - 1
	i -= 1
print(min_tape)


def main():
	[n, m, k] = list(map(int, input().split(' ')))
	ar = list(map(int, input().split(' ')))
	diff = []
	prev = ar[0]
	for i in range(1, len(ar)):
		diff.append(ar[i] - prev)
		prev = ar[i]
	diff.sort()
	sumofdiff = sum(diff[:n - k])
	result = sumofdiff + k
	print(result)
	return
main()


from sys import stdin, stdout
from itertools import combinations
from collections import defaultdict

def listIn():
	return list(map(int, stdin.readline().strip().split()))

def stringListIn():
	return [x for x in stdin.readline().split()]

def intIn():
	return int(stdin.readline())

def stringIn():
	return stdin.readline().strip()
(n, m, k) = listIn()
b = listIn()
if n == k:
	print(n)
else:
	diff = []
	for i in range(1, n):
		diff.append(b[i] - b[i - 1])
	a = sorted(diff)
	c = 0
	ans = sum(a[:n - k])
	print(ans + k)


(n, tape, cut) = map(int, input().split())
lst = [int(x) for x in input().split()]
largest_cut = lst[n - 1] - lst[0] + 1
mst = [lst[x + 1] - lst[x] - 1 for x in range(0, n - 1)]
mst = sorted(mst, reverse=True)
print(largest_cut - sum(mst[0:cut - 1]))


I = lambda : map(int, input().split())
(n, m, k) = I()
li = list(I())
diff = []
if k >= n:
	exit(print(n))
for i in range(1, len(li)):
	t = li[i] - li[i - 1]
	diff.append(t)
diff.sort()
ans = n
t = n
for i in diff:
	t = t - 1
	ans = ans + i - 1
	if t == k:
		exit(print(ans))


import os
import sys
import math
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
d = [] * (n - 1)
for i in range(1, n):
	t = a[i] - a[i - 1] - 1
	d.append(t)
d.sort()
count = n
j = n - k
for i in range(j):
	count += d[i]
print(count)


(n, m, k) = map(int, input().split())
b = list(map(int, input().split()))
sab = [b[i + 1] - b[i] for i in range(len(b) - 1)]
sortsab = sorted(sab)
sumtape = 0
for i in range(n - k):
	sumtape += sortsab[i]
sumtape += k
print(sumtape)


import sys
import math
line = input()
(n, m, k) = [int(x) for x in line.split()]
line = input()
numbers = [int(x) for x in line.split()]
diffs = []
for i in range(0, len(numbers) - 1):
	diffs.append(numbers[i + 1] - numbers[i])
diffs = sorted(diffs)
if k == 1:
	print(sum(diffs) + 1)
else:
	print(sum(diffs[0:-k + 1]) + k)


(a, b, c) = map(int, input().split())
A = list(map(int, input().split()))
B = []
for i in range(a - 1):
	B.append(A[i + 1] - A[i] - 1)
B.sort()
B.reverse()
j = c - 1
q = A[-1] - A[0] + 1
q -= sum(B[:j])
print(q)


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


import sys
import math
sys.setrecursionlimit(100000)
input = sys.stdin.readline

def inp():
	return int(input())

def inara():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
(n, m, k) = invr()
ara = inara()
if k == n:
	print(n)
	exit(0)
diff = [0] * n
for i in range(1, n):
	diff[i - 1] = ara[i] - ara[i - 1]
diff.sort(reverse=True)
ans = ara[n - 1] - ara[0]
for i in range(k - 1):
	ans -= diff[i]
ans += k
print(ans)


def read_int():
	return int(input().strip())

def read_string():
	return input().strip()

def read_int_list():
	return list(map(int, input().strip().split()))

def read_string_list():
	return input().strip().split()
import sys
(n, m, k) = read_int_list()
points = read_int_list()
covered_pts = set()

def calc_cost(segments):
	segments.sort(key=lambda x: x[0])
	out = 0
	(prev_start, prev_end, prev_cost) = segments[0]
	covered_pts.add(prev_start)
	covered_pts.add(prev_end)
	for i in range(1, len(segments)):
		(start, end, cost) = segments[i]
		covered_pts.add(start)
		covered_pts.add(end)
		if start <= prev_end and start >= prev_start:
			prev_end = end
			continue
		else:
			out += prev_end - prev_start + 1
			(prev_start, prev_end) = (start, end)
	out += prev_end - prev_start + 1
	return out
if k >= n:
	print(k)
	sys.exit()
segments = []
for i in range(n - 1):
	segments.append([points[i], points[i + 1], points[i + 1] - points[i]])
segments.sort(key=lambda x: x[2])
ret = calc_cost(segments[:n - k])
count = 0
for p in points:
	if p not in covered_pts:
		count += 1
print(ret + count)


(n, m, k) = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
b = sorted(b)
l = []
for i in range(len(b) - 1):
	l.append(b[i + 1] - b[i])
l = sorted(l)
ans = min(n, k)
if n > k:
	diff = n - k
	ans += sum(l[:diff])
print(ans)


import sys
lne = [int(i) for i in sys.stdin.readline().rstrip().split(' ')]
l = [int(i) for i in sys.stdin.readline().rstrip().split(' ')]
count = len(l)
newL = []
for i in range(1, len(l)):
	newL.append(l[i] - l[i - 1])
newL = sorted(newL)
count += sum([i - 1 for i in newL[0:lne[0] - lne[2]]])
print(count)


(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())
b = list(map(int, input().split()))
diff = []
for i in range(1, n):
	diff.append(b[i] - b[i - 1])
diff.sort()
s = 0
for i in range(n - k):
	s += diff[i]
print(s + k)


(n, m, k) = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
d = [b[i] - b[i - 1] for i in range(1, n)]
sd = sorted(d)
sdi = [i[0] for i in sorted(enumerate(d), key=lambda x: x[1])]
for x in range(k - 1):
	d[sdi[-(x + 1)]] = -1
ans = 0
for i in range(len(d)):
	if d[i] == -1:
		ans += 1
	else:
		ans += d[i]
print(ans + 1)


def lenta(lst, K):
	differences = [0] * (len(lst) - 1)
	for i in range(1, len(lst)):
		differences[i - 1] = lst[i] - lst[i - 1]
	return sum(sorted(differences)[:len(lst) - K]) + K
(n, m, k) = [int(j) for j in input().split()]
a = [int(x) for x in input().split()]
print(lenta(a, k))


(n, m, k) = map(int, input().split())
seq = list(map(int, input().split()))
seg = []
for i in range(len(seq) - 1):
	seg.append([seq[i + 1] - seq[i] + 1, i])
seg = sorted(seg)
fixed = [1 for x in range(n)]
ans = 0
i = 0
while i < n - k:
	ans += seg[i][0]
	if fixed[seg[i][1]] == 0:
		ans -= 1
	if fixed[seg[i][1] + 1] == 0:
		ans -= 1
	fixed[seg[i][1]] = 0
	fixed[seg[i][1] + 1] = 0
	i += 1
ans += sum(fixed)
print(ans)


s1 = input().split()
s2 = input().split()
n = int(s1[0])
m = int(s1[1])
k = int(s1[2])
a = list(s2)
dis = []
length = len(a)
for i in range(0, n):
	dis.append(0)
ans = n
for i in range(1, n):
	dis[i] = int(a[i]) - int(a[i - 1]) - 1
dis.sort()
for i in range(1, n - k + 1):
	ans += dis[i]
print(ans)


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


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 os
import sys
from io import BytesIO, IOBase
import math
from itertools import permutations
from decimal import Decimal, getcontext
getcontext().prec = 25
MOD = pow(10, 9) + 7
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m, k) = map(int, input().split(' '))
l = list(map(int, input().split(' ')))
b = [0] * (n - 1)
for i in range(n - 1):
	b[i] = l[i + 1] - l[i]
b.sort()
print(sum(b[:n - k]) + k)