AtCoder Beginner Contest 117 - Streamline

We will play a one-player game using a number line and N pieces.
First, we place each of these pieces at some integer coordinate.
Here, multiple pieces can be placed at the same coordinate.
Our objective is to visit all of the M coordinates X_1, X_2, ..., X_M with these pieces, by repeating the following move:
Move: Choose a piece and let x be its coordinate. Put that piece at coordinate x+1 or x-1.
Note that the coordinates where we initially place the pieces are already regarded as visited.
Find the minimum number of moves required to achieve the objective.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 10^5
 - 1 \leq M \leq 10^5
 - -10^5 \leq X_i \leq 10^5
 - X_1, X_2, ..., X_M are all different.

-----Input-----
Input is given from Standard Input in the following format:
N M
X_1 X_2 ... X_M

-----Output-----
Find the minimum number of moves required to achieve the objective.

-----Sample Input-----
2 5
10 12 1 2 14

-----Sample Output-----
5

The objective can be achieved in five moves as follows, and this is the minimum number of moves required.
 - Initially, put the two pieces at coordinates 1 and 10.
 - Move the piece at coordinate 1 to 2.
 - Move the piece at coordinate 10 to 11.
 - Move the piece at coordinate 11 to 12.
 - Move the piece at coordinate 12 to 13.
 - Move the piece at coordinate 13 to 14.

Difficulty: EASY

Starter code:

Solutions:
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
y = []
for i in range(len(x) - 1):
	y += [x[i + 1] - x[i]]
y.sort()
if n >= m:
	print(0)
else:
	print(sum(y[:m - n]))


(n, m) = list(map(int, input().split()))
dots = list(map(int, input().split()))
if n >= m:
	print(0)
else:
	dots.sort()
	if n == 1:
		print(dots[-1] - dots[0])
	else:
		dot_diffs = [[i, dots[i + 1] - dots[i]] for i in range(len(dots) - 1)]
		dot_diffs.sort(key=lambda x: -x[1])
		ans = 0
		for (idx, i) in enumerate(dot_diffs[0:n - 1]):
			if idx == 0:
				ans += dots[i[0]] - dots[0]
			else:
				ans += dots[i[0]] - dots[prev[0] + 1]
			prev = i
		ans += dots[-1] - dots[dot_diffs[0:n - 1][-1][0] + 1]
		print(ans)


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
Y = []
for i in range(M - 1):
	Y.append(X[i + 1] - X[i])
Y.sort(reverse=True)
print(sum(Y[N - 1:]))


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


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


(N, M) = map(int, input().split())
X = sorted(map(int, input().split()))
dist = sorted([X[i + 1] - X[i] for i in range(M - 1)])[::-1]
print(sum(dist[N - 1:]))


(n, m) = map(int, input().split())
X = sorted(map(int, input().split()))
D = []
for i in range(m - 1):
	D.append(X[i + 1] - X[i])
print(sum(sorted(D)[::-1][n - 1:]))


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
L = sorted([X[i + 1] - X[i] for i in range(M - 1)], reverse=True)
print(sum(L[N - 1:]))


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
Y = [X[i + 1] - X[i] for i in range(M - 1)]
Y.sort()
if M <= N:
	print(0)
else:
	print(sum(Y[:M - N]))


(N, M) = map(int, input().split())
X = map(int, input().split())
X = sorted(X)
V = sorted((y - x for (x, y) in zip(X[:-1], X[1:])))
print(max(X) - min(X) - sum(V[max(0, len(V) - N + 1):]))


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


(N, M) = map(int, input().split())
X = sorted(list(map(int, input().split())))
chk = sorted([X[i + 1] - X[i] for i in range(M - 1)])
print(sum(chk[:max(M - N, 0)]))


(n, m) = map(int, input().split())
a = sorted(list(map(int, input().split())))
dst = [0] * (m - 1)
for i in range(m - 1):
	dst[i] = abs(a[i + 1] - a[i])
dst.sort(reverse=True)
print(sum(dst[n - 1:]))


(n, m) = map(int, input().split())
xx = sorted(list(map(int, input().split())))
yy = [abs(xx[i] - xx[i + 1]) for i in range(m - 1)]
sy = sorted(yy)
if n > 1:
	print(sum(sy[:-n + 1]))
else:
	print(xx[-1] - xx[0])


(N, M) = list(map(int, input().split()))
X = sorted(list(map(int, input().split())))
D = sorted([X[i + 1] - X[i] for i in range(M - 1)])
print(0 if M <= N else sum(D[:M - N]))


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


(n, m) = map(int, input().split())
x = sorted(list(map(int, input().split())))
d = []
if n >= m or m == 1:
	print(0)
elif n < m:
	for i in range(m - 1):
		d.append(x[i + 1] - x[i])
	print(sum(sorted(d)[:m - n]))


import sys
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
if n >= m or m == 1:
	print('0')
	return
x.sort()
c = []
for i in range(1, m):
	c.append(abs(x[i] - x[i - 1]))
c.sort()
print(sum(c[:len(c) - n + 1]))


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
D = [abs(X[i] - X[i + 1]) for i in range(M - 1)]
D.sort(reverse=True)
print(sum(D[N - 1:]))


(n, m) = map(int, input().split())
x = sorted(map(int, input().split()))
if n >= m:
	print(0)
else:
	d = sorted([x[i] - x[i - 1] for i in range(1, m)])
	print(sum(d[:m - 1 - (n - 1)]))


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
x_dif = [b - a for (a, b) in zip(x[:-1], x[1:])]
x_dif.sort(reverse=True)
print(sum(x_dif[n - 1:]))


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, M, *X) = list(map(int, read().split()))
	if N >= M:
		print(0)
		return
	X.sort()
	dist = [0] * (M - 1)
	for i in range(M - 1):
		dist[i] = X[i + 1] - X[i]
	dist.sort()
	ans = sum(dist[:M - N])
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
Xd = [X[i + 1] - X[i] for i in range(M - 1)]
Xd.sort()
print(sum(Xd[:max(M - N, 0)]))


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
diff = [X[i] - X[i - 1] for i in range(1, M)]
diff.sort()
if N != 1:
	del diff[-N + 1:]
print(sum(diff))


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
Y = []
for (a, b) in zip(X, X[1:]):
	Y.append(b - a)
Y.sort()
print(sum(Y[:max(0, M - N)]))


import math
(n, m) = map(int, input().split(' '))
xL = sorted(list(map(int, input().split(' '))))
diff = [0 for _ in range(m - 1)]
for i in range(m - 1):
	diff[i] = xL[i + 1] - xL[i]
diff = sorted(diff, reverse=True)
print(sum(diff[n - 1:]))


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
x = sorted(x)
y = [abs(i - j) for (i, j) in zip(x[1:], x[:-1])]
y = sorted(y)
z = sum(y[:m - n])
print(z if n < m else 0)


(n, m, *x) = map(int, open(0).read().split())
x.sort()
print(sum(sorted([j - i for (i, j) in zip(x, x[1:])])[:max(0, m - n)]))


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


(N, M) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
l = [0] * M
for i in range(1, M):
	l[i] = x[i] - x[i - 1]
l.sort(reverse=True)
print(sum(l[N - 1:]))


(N, M) = map(int, input().split())
X = sorted(map(int, input().split()))
D = sorted((x2 - x1 for (x1, x2) in zip(X, X[1:])))[::-1]
print(sum(D[N - 1:]))


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


(n, m, *a) = map(int, open(0).read().split())
a.sort()
print(sum(sorted([a[i + 1] - a[i] for i in range(m - 1)])[:max(0, m - n)]))


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
P = [X[i + 1] - X[i] for i in range(M - 1)]
P.sort()
P = P[::-1]
print(sum(P[N - 1:]))


I = lambda : map(int, input().split())
(N, M) = I()
X = sorted(I())
print(sum(sorted((X[i + 1] - X[i] for i in range(M - 1)))[:max(M - N, 0)]))


(N, M) = map(int, input().split())
X = sorted(map(int, input().split()))
sub = [X[i + 1] - X[i] for i in range(M - 1)]
sub.sort()
if M >= N:
	print(sum(sub[:M - N]))
else:
	print(0)


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


def main():
	(n, m) = list(map(int, input().split()))
	x = sorted(list(map(int, input().split())))
	diff = list()
	for (i, j) in zip(x, x[1:]):
		diff.append(abs(i - j))
	diff = sorted(diff, reverse=True)
	print(sum(diff) - sum(diff[:n - 1]))

def __starting_point():
	main()
__starting_point()


(N, M) = list(map(int, input().split()))
X = list(map(int, input().split()))
X.sort()
D = [r - l for (l, r) in zip(X, X[1:])]
D.sort()
ans = sum(D)
while D and N > 1:
	N -= 1
	ans -= D.pop()
print(ans)


(N, M) = map(int, input().split())
X = sorted(list(map(int, input().split())))
dif_X = sorted([X[i + 1] - x for (i, x) in enumerate(X[:-1])])
print(sum(dif_X[:max(0, M - N)]))


import sys
(N, M) = list(map(int, input().split()))
if M < N:
	print(0)
	return
X = list(map(int, input().split()))
X.sort()
ls = []
for i in range(M - 1):
	ls.append(X[i + 1] - X[i])
ls.sort(reverse=True)
print(X[M - 1] - X[0] - sum(ls[:N - 1]))


(n, m) = map(int, input().split())
x = sorted(list(map(int, input().split())))
d = sorted([x[i + 1] - x[i] for i in range(m - 1)])
print(sum(d[:max(0, m - n)]))


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


(n, m) = map(int, input().split())
Xm = list(map(int, input().split()))
Xm.sort()
check = [Xm[i + 1] - Xm[i] for i in range(m - 1)]
check.sort()
print(sum(check[:max(m - n, 0)]))


(N, M) = map(int, input().split())
(*X,) = sorted(map(int, input().split()))
print(sum(sorted([abs(X[i + 1] - X[i]) for i in range(M - 1)], reverse=True)[N - 1:]))


import sys
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
if n >= m:
	print(0)
	return
dis = [x[i + 1] - x[i] for i in range(m - 1)]
dis.sort()
print(sum(dis[:m - n]))


(N, M) = list(map(int, input().split()))
X = list(map(int, input().split()))
Y = []
X.sort()
ans = 0
if N >= M:
	print(0)
	return
for i in range(M - 1):
	Y.append(X[i + 1] - X[i])
Y.sort(reverse=True)
for j in range(N - 1):
	ans += Y[j] - 1
print(X[M - 1] - X[0] + 1 - ans - N)


def readinput():
	(n, m) = list(map(int, input().split()))
	x = list(map(int, input().split()))
	return (n, m, x)

def main(n, m, x):
	if m <= n:
		return 0
	xs = sorted(x)
	d = []
	for i in range(m - 1):
		d.append((xs[i + 1] - xs[i], i + 1))
	ds = sorted(d, reverse=True, key=lambda x: x[0])
	c = [0] * m
	for i in range(n - 1):
		c[ds[i][1]] += 1
	ans = 0
	for i in range(1, m):
		if c[i] == 0:
			ans += xs[i] - xs[i - 1]
	return ans

def __starting_point():
	(n, m, x) = readinput()
	ans = main(n, m, x)
	print(ans)
__starting_point()


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


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


import sys
sys.setrecursionlimit(10 ** 8)
ini = lambda : int(sys.stdin.readline())
inl = lambda : [int(x) for x in sys.stdin.readline().split()]
ins = lambda : sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print('\x1b[33m', *a, '\x1b[0m', **dict(file=sys.stderr, **kw))

def solve():
	(n, m) = inl()
	X = inl()
	X.sort()
	x = X[0]
	D = []
	for i in range(1, m):
		d = X[i] - x
		D.append(d)
		x = X[i]
	D.sort()
	k = max(m - n, 0)
	return sum(D[:k])
print(solve())


(n, m) = list(map(int, input().split()))
x = list(map(int, input().split()))
if n >= m:
	print(0)
	return
x.sort()
l = []
for i in range(m - 1):
	l.append(x[i + 1] - x[i])
l.sort(reverse=True)
ans = x[m - 1] - x[0]
for i in range(n - 1):
	ans -= l[i]
print(ans)


(N, M) = map(int, input().split())
X = [int(x) for x in input().split()]

def solve():
	if N >= M:
		return 0
	X.sort()
	d = [X[i + 1] - X[i] for i in range(M - 1)]
	d.sort()
	return sum(d[0:M - N])
print(solve())


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
A = list((y - x for (x, y) in zip(X, X[1:])))
A.sort(reverse=True)
print(sum(iter(A[N - 1:])))


(n, m) = list(map(int, input().split()))
x = list(map(int, input().split()))
if n >= m:
	print(0)
	return
x.sort()
dists = []
point = x.pop(0)
for xs in x:
	dists.append(xs - point)
	point = xs
dists.sort(reverse=True)
print(sum(dists[n - 1:]))


(N, M) = list(map(int, input().split()))
X = sorted(list(map(int, input().split())))
kyori = []
for i in range(M - 1):
	kyori.append(X[i + 1] - X[i])
if N == 1:
	print(sum(kyori))
else:
	print(sum(sorted(kyori)[:-N + 1]))


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


(n, m) = map(int, input().split())
(*a,) = map(int, input().split())
a.sort()
d = [a[i + 1] - a[i] for i in range(m - 1)]
d = sorted(d, reverse=True)
if m <= n:
	print(0)
else:
	print(sum(d[n - 1:]))


(n, m) = map(int, input().split())
x = sorted(list(map(int, input().split())))
if n >= m:
	print(0)
else:
	nums = [0] * (m - 1)
	for i in range(m - 1):
		nums[i] = x[i + 1] - x[i]
	nums.sort()
	print(sum(nums[:m - n]))


(n, m, *x) = map(int, open(0).read().split())
x.sort()
print(sum(sorted([x[i + 1] - x[i] for i in range(m - 1)])[:m - n]) if n < m else 0)


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


(n, m, *a) = map(int, open(0).read().split())
a.sort()
b = [i - j for (i, j) in zip(a[1:], a)]
b.sort()
print(sum(b[:max(0, m - n)]))


(N, M) = map(int, input().split())
X = sorted(list(map(int, input().split())))
d = [0] * (M - 1)
for i in range(len(X) - 1):
	d[i] = X[i + 1] - X[i]
d = sorted(d)[::-1]
print(sum(d[N - 1:]))


from operator import sub
(N, M) = map(int, input().split())
X = sorted(map(int, input().split()))
print(sum(sorted(map(sub, X[1:], X), reverse=True)[N - 1:]))


(N, M) = map(int, input().split())
X = sorted(map(int, input().split()))
s = []
for i in range(M - 1):
	s.append(X[i + 1] - X[i])
s = sorted(s)[::-1]
print(sum(s[N - 1:]))


(N, M, *X) = map(int, open(0).read().split())
X.sort()
print(0 if N >= M else sum(sorted((abs(X[i + 1] - X[i]) for i in range(M - 1)))[:M - N]))


(N, M) = map(int, input().split())
X = sorted(list(map(int, input().split())))
h = []
ans = 0
if N < M:
	for i in range(M - 1):
		h.append(X[i + 1] - X[i])
	h = sorted(h)
	ans = max(ans, sum(h[:M - N]))
print(ans)


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


(N, M, *X) = map(int, open(0).read().split())
X.sort()
y = sorted([X[i + 1] - X[i] for i in range(len(X) - 1)], reverse=True)
print(sum(y[N - 1:]))


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


(N, M) = list(map(int, input().split()))
X = sorted(list(map(int, input().split())))
B = []
if N >= M:
	print(0)
else:
	for i in range(M - 1):
		B.append(X[i + 1] - X[i])
	B.sort()
	print(sum(B[:M - N]))


def main():
	(n, m) = list(map(int, input().split()))
	pos_list = list(map(int, input().split()))
	pos_list.sort()
	if n >= m:
		return 0
	diff_list = [0]
	for i in range(m - 1):
		diff_list.append(pos_list[i + 1] - pos_list[i])
	diff_list.sort()
	if n == 1:
		return sum(diff_list)
	return sum(diff_list[:-n + 1])
print(main())


(n, m) = map(int, input().split())
li_X = list(map(int, input().split()))
li_X.sort()
li_X_delta = []
for i in range(len(li_X) - 1):
	li_X_delta.append(li_X[i + 1] - li_X[i])
li_X_delta.sort(reverse=True)
cnt = 0
ans = li_X[-1] - li_X[0]
for i in range(min(n - 1, len(li_X_delta))):
	ans -= li_X_delta[i]
print(ans)


(n, m) = map(int, input().split())
xl = list(map(int, input().split()))
xl.sort()
difl = []
for i in range(1, m):
	difl.append(xl[i] - xl[i - 1])
difl.sort(reverse=True)
if n >= m:
	ans = 0
else:
	ans = xl[-1] - xl[0] - sum(difl[:n - 1])
print(ans)


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


(N, M) = map(int, input().split())
X = sorted(list(map(int, input().split())))
tmp = sorted([X[i + 1] - X[i] for i in range(M - 1)])
ans = sum(tmp[:M - N])
if M <= N:
	ans = 0
print(ans)


(N, M) = [int(i) for i in input().split()]
if N >= M:
	print(0)
	exit()
L = [int(i) for i in input().split()]
L.sort()
X = [L[i + 1] - L[i] for i in range(M - 1)]
X.sort()
print(sum(X[:M - N]))


(n, m) = map(int, input().split())
al = list(map(int, input().split()))
if n >= m:
	print(0)
	return
al_s = sorted(al)
res = []
for i in range(m - 1):
	res.append(al_s[i + 1] - al_s[i])
res_s = sorted(res)
print(sum(res) - sum(res_s[m - n:]))


(n, m) = map(int, input().split())
x = [int(i) for i in input().split()]
x.sort()
if n >= m:
	ans = 0
else:
	x_sa = [x[i + 1] - x[i] for i in range(m - 1)]
	x_sa.sort(reverse=True)
	if n > 1:
		del x_sa[:n - 1]
	ans = sum(x_sa)
print(ans)


(n, m) = map(int, input().split())
if n >= m:
	print(0)
	exit()
x = sorted(map(int, input().split()))
l = sorted((i - j for (i, j) in zip(x[1:], x[:-1])))
print(sum(l[:m - n]))


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
if n >= m:
	print(0)
	return
data = [0] * (m - 1)
for i in range(m - 1):
	data[i] = x[i + 1] - x[i]
data.sort()
res = 0
for i in range(n - 1):
	res += data[m - 2 - i]
print(sum(data) - res)


(N, M) = map(int, input().split())
X = sorted(list(map(int, input().split())))
x = []
for i in range(M - 1):
	x.append(abs(X[i + 1] - X[i]))
x = sorted(x)[::-1]
print(sum(x[N - 1:]))


(N, M) = list(map(int, input().split()))
X = list(map(int, input().split()))
X.sort()
cnt = 0
arr = [0] * (M - 1)
if N >= M:
	ans = 0
else:
	for i in range(1, M):
		arr[i - 1] = abs(X[i - 1] - X[i])
	arr.sort()
	ans = sum(arr[0:M - N])
print(ans)


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


(n, m) = list(map(int, input().split()))
l = list(map(int, input().split()))
if n >= m:
	print(0)
else:
	num = n - 1
	sl = sorted(l)
	dsl = [abs(sl[i + 1] - sl[i]) for i in range(m - 1)]
	dsl = sorted(dsl)
	print(sum(dsl[0:len(dsl) - num]))


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
cost = [0] * (M - 1)
for i in range(M - 1):
	cost[i] = X[i + 1] - X[i]
cost.sort(reverse=True)
print(sum(cost[N - 1:]))


(n, m) = map(int, input().split())
xl = sorted(list(map(int, input().split())))
diff = [0] * (m - 1)
for i in range(m - 1):
	diff[i] = xl[i + 1] - xl[i]
diff_s = sorted(diff, reverse=True)
print(sum(diff_s[n - 1:]))


(N, M) = map(int, input().split())
X = sorted(map(int, input().split()))
diff = [0] * (M - 1)
for i in range(M - 1):
	diff[i] = X[i + 1] - X[i]
print(sum(sorted(diff)[::-1][N - 1:]))


from sys import stdin
(n, m, *x) = map(int, stdin.read().split())
x.sort()
y = [x[i] - x[i - 1] for i in range(1, m)]
y.sort()
print(sum(y[:m - n]) if n < m else 0)


(N, M) = map(int, input().split(' '))
A = list(sorted(map(int, input().split(' '))))
L = sorted([A[s] - A[s + 1] for s in range(M - 1)])
print(abs(sum(L[N - 1:])))


(N, M) = map(int, input().split())
list = list(map(int, input().split()))
list.sort()
dif = [b - a for (a, b) in zip(list, list[1:])]
dif.sort()
print(sum(dif[:M - N]) if M - N > 0 else 0)


(n, m) = map(int, input().split())
X = sorted(list(map(int, input().split())))
A = []
for (a, b) in zip(X, X[1:]):
	A.append(b - a)
A.sort()
print(sum(A[:m - n]) if m - n > 0 else 0)


(n, m, *xx) = map(int, open(0).read().split())
xx.sort()
diff = [a - b for (a, b) in zip(xx[1:], xx[:-1])]
diff.sort(reverse=True)
print(sum(diff[n - 1:]))


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
ans = 0
if n < m:
	x.sort()
	l = [x[i + 1] - x[i] for i in range(m - 1)]
	l.sort()
	ans = max(x) - min(x)
	for i in range(n - 1):
		ans -= l[-1 - i]
print(ans)


(N, M) = list(map(int, input().split()))
if N > M:
	print(0)
	return
lst = list(map(int, input().split()))
lst.sort()
sum_1 = max(lst) - min(lst)
D = []
for i in range(1, M):
	D.append(lst[i] - lst[i - 1])
D.sort(reverse=True)
sum_2 = 0
for i in range(N - 1):
	sum_2 += D[i]
ans = 0
ans = sum_1 - sum_2
print(ans)


import numpy as np
(N, M) = list(map(int, input().split()))
X = list(map(int, input().split()))
sortX = np.array(sorted(X), dtype=np.int64)
diffX = np.sort(np.diff(sortX))
if N == 1:
	print(np.sum(diffX))
	return
ans = np.sum(diffX[:-(N - 1)])
print(ans)


def inpl():
	return [int(i) for i in input().split()]
(N, M) = inpl()
X = inpl()
X.sort()
X = [j - i for (i, j) in zip(X, X[1:])]
X.sort(reverse=True)
print(sum(X[N - 1:]))


(n, m) = list(map(int, input().split()))
x = sorted(list(map(int, input().split())))
y = []
if n > m:
	print(0)
	return
for i in range(m - 1):
	diff = x[i + 1] - x[i]
	y.append(diff)
y.sort(reverse=True)
res = x[-1] - x[0]
for i in range(n - 1):
	res -= y[i]
print(res)


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
if N >= M:
	print(0)
	return
X.sort()
a = []
for i in range(M - 1):
	a.append(abs(X[i] - X[i + 1]))
a.sort()
ans = 0
for i in range(M - N):
	ans += a[i]
print(ans)


(n, m) = map(int, input().split())
a = sorted(map(int, input().split()))
p = []
for x in range(m - 1):
	p.append(a[x + 1] - a[x])
if n == 1:
	print(sum(p))
	exit()
print(sum(sorted(p)[:1 - n]))


(N, M) = map(int, input().split())
X = sorted(list(map(int, input().split())))
L = []
for i in range(1, M):
	L.append(X[i] - X[i - 1])
L = sorted(L, reverse=True)
if N >= M:
	print(0)
else:
	print(sum(L[N - 1:]))


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


(N, M) = map(int, input().split())
if N >= M:
	print(0)
	exit()
X = sorted(map(int, input().split()))
L = [X[m + 1] - X[m] for m in range(M - 1)]
L.sort()
print(sum(L[:M - N]))


(n, m) = map(int, input().split())
x_l = list(map(int, input().split()))
x_l = sorted(x_l)
sub_l = sorted([x_l[i + 1] - x_l[i] for i in range(m - 1)])
if n >= m:
	ans = 0
else:
	r = m - n
	ans = sum(sub_l[:r])
print(ans)


(n, k) = list(map(int, input().split(' ')))
l = sorted(list(map(int, input().split(' '))))
print(sum(sorted([l[i + 1] - l[i] for i in range(len(l) - 1)])[:max(0, k - n)]))


(n, m) = map(int, input().split())
X = list(map(int, input().split()))
if n >= m:
	print(0)
else:
	X.sort()
	dis = [X[i] - X[i - 1] for i in range(1, m)]
	dis.sort()
	print(sum(dis[:m - n]))


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


(n, m) = [int(e) for e in input().split()]
a = sorted([int(e) for e in input().split()])
l = sum(sorted([y - x for (x, y) in zip(a, a[1:])], reverse=True)[:n - 1])
print(max(a) - min(a) - l)


(N, M) = list(map(int, input().split()))
X = list(map(int, input().split()))
sortX = sorted(X)
diffX = [sortX[i] - sortX[i - 1] for i in range(1, M)]
sdiffX = sorted(diffX)
if N == 1:
	print(sum(sdiffX))
	return
ans = sum(sdiffX[:-(N - 1)])
print(ans)


def mapt(fn, *args):
	return tuple(map(fn, *args))

def Input():
	return mapt(int, input().split(' '))

def main():
	(n, m) = Input()
	x = sorted(Input())
	data = sorted((abs(x[i] - x[i + 1]) for i in range(m - 1)), reverse=True)
	print(sum(data[n - 1:]))
main()


(n, m) = map(int, input().split())
X = sorted(list(map(int, input().split())))
if n >= m:
	print(0)
else:
	d = sorted([i - j for (i, j) in zip(X[1:], X)])
	print(sum(d[:m - n]))


(n, m, *x) = map(int, open(0).read().split())
if n >= m:
	print(0)
	exit(0)
x = sorted(x)
s = []
for i in range(m - 1):
	s.append(x[i + 1] - x[i])
s.sort()
print(sum(s[:m - n]))


(N, M, *X) = list(map(int, open(0).read().split()))
if N >= M:
	print(0)
	return
X.sort()
diff = []
for i in range(M - 1):
	diff.append(X[i + 1] - X[i])
diff.sort()
print(sum(diff[:M - N]))


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


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


def main():
	(n, m) = list(map(int, input().split()))
	x = sorted(map(int, input().split()))
	x_dist = sorted([x[i] - x[i - 1] for i in range(1, m)], reverse=True)
	print(x[-1] - x[0] - sum(x_dist[:n - 1]))

def __starting_point():
	main()
__starting_point()


(n, m) = list(map(int, input().split()))
x = list(map(int, input().split()))
x.sort()
total = max(x) - min(x)
if n >= m:
	print(0)
elif n == 1:
	print(total)
else:
	gap = []
	for (i, j) in zip(x, x[1:]):
		gap.append(j - i)
	gap.sort(reverse=True)
	print(total - sum(gap[:n - 1]))


(n, m) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
Xx = sorted([X[i + 1] - X[i] for i in range(m - 1)], reverse=True)
print(sum(Xx[n - 1:]))


def main():
	import sys
	pin = sys.stdin.readline
	pout = sys.stdout.write
	perr = sys.stderr.write
	(N, M) = list(map(int, pin().split()))
	X = list(map(int, pin().split()))
	if N >= M:
		print(0)
		return
	X.sort()
	d = []
	for i in range(M - 1):
		d.append(abs(X[i] - X[i + 1]))
	d.sort()
	print(sum(d[:M - N]))
	return
main()


import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
input = sys.stdin.readline

def RD():
	return input().rstrip()

def F():
	return float(input().rstrip())

def I():
	return int(input().rstrip())

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

def MF():
	return map(float, input().split())

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

def TI():
	return tuple(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def Init(H, W, num):
	return [[num for i in range(W)] for j in range(H)]

def main():
	(N, M) = MI()
	L = sorted(LI())
	L2 = []
	past = L[0]
	if M == 1:
		print(0)
		return
	for i in L[1:]:
		L2.append(i - past)
		past = i
	L2.sort(reverse=True)
	res = sum(L2)
	num = N - 1
	if num >= M:
		num = M - 1
	for i in range(num):
		res -= L2[i]
	print(res)

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
x = sorted(list(map(int, input().split())))
if n >= m:
	print(0)
else:
	dist = [abs(x[i + 1] - x[i]) for i in range(m - 1)]
	dist = sorted(dist)
	print(sum(dist[:m - n]))


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
if N >= M:
	print(0)
elif N == 1:
	print(abs(max(X) - min(X)))
else:
	load = [X[i] - X[i - 1] for i in range(1, M)]
	load.sort()
	print(sum(load[:M - N]))


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


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
dif = []
for i in range(m - 1):
	dif.append(x[i] - x[i + 1])
dif.sort()
ans = abs(sum(dif[n - 1:]))
print(ans)


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


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


(n, m) = list(map(int, input().split()))
X = list(map(int, input().split()))
if m == 1:
	print(0)
	return
X.sort()
D = []
for i in range(1, m):
	D.append(X[i] - X[i - 1])
D.sort(reverse=True)
d = 0
if i > 1:
	for i in range(min(n - 1, m - 1)):
		d += D[i]
ans = sum(D) - d
print(ans)


(N, M) = map(int, input().split())
X = sorted(map(int, input().split()))
d = sorted((j - i for (i, j) in zip(X, X[1:])))[::-1]
print(sum(d[N - 1:]))


(n, m, *x) = map(int, open(0).read().split())
x.sort()
d = [x[i + 1] - x[i] for i in range(m - 1)]
d.sort(reverse=True)
print(sum(d[n - 1:]))


import sys
(N, M) = map(int, input().split())
x = list(map(int, input().split()))
X = sorted(x)
D = [0] * (M - 1)
if N >= M:
	print(0)
	return
for i in range(M - 1):
	D[i] = X[i + 1] - X[i]
new_D = sorted(D)
cnt = 0
for i in range(M - N):
	cnt = cnt + new_D[i]
print(cnt)


import sys
(N, M) = map(int, input().split())
L = list(map(int, input().split()))
if N >= M:
	print(0)
	return
L.sort()
K = []
s = 0
for i in range(M - 1):
	K.append(L[i + 1] - L[i])
K.sort(reverse=True)
for i in range(N - 1):
	s += K[i]
print(L[M - 1] - L[0] - s)


(N, M) = map(int, input().split())
x = sorted(map(int, input().split()))
diff = sorted([x[i + 1] - x[i] for i in range(M - 1)], reverse=True)
print(sum(diff[N - 1:]))


(N, M) = list(map(int, input().split()))
X = sorted(list(map(int, input().split())))
I = sorted([X[m + 1] - X[m] for m in range(M - 1)])
print(sum(I[:max(M - N, 0)]))


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
xs = sorted(X)
d = []
for i in range(M - 1):
	d.append(xs[i + 1] - xs[i])
ds = sorted(d)
if M > N:
	print(sum(ds[:M - N]))
else:
	print(0)


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
if n >= m:
	print('0')
	return
x_sorted = sorted(x)
dx = [abs(x_sorted[i + 1] - x_sorted[i]) for i in range(m - 1)]
dx_sorted = sorted(dx, reverse=True)
result = sum(dx_sorted)
for i in range(n - 1):
	result -= dx_sorted[i]
print(result)


(N, M) = map(int, input().split())
X = sorted(list(map(int, input().split())))
sabun = sorted([X[i + 1] - X[i] for i in range(M - 1)], reverse=True)
print(X[-1] - X[0] - sum(sabun[:N - 1]))


(N, M) = map(int, input().split())
X = [int(x) for x in input().split()]
X.sort()
length = [x - X[i] for (i, x) in enumerate(X[1:])]
length.sort(reverse=True)
print(sum(length[N - 1:]))


(N, M) = map(int, input().split())
X = sorted(list(map(int, input().split())))
Y = sorted([X[i + 1] - X[i] for i in range(M - 1)])[::-1]
print(max(X) - min(X) - sum(Y[:N - 1]))


from itertools import tee

def pairwise(iterable):
	(a, b) = tee(iterable)
	next(b, None)
	return list(zip(a, b))
(N, M, *X) = list(map(int, open(0).read().split()))
if N >= M:
	print(0)
	return
X.sort()
diffs = [cur - prev for (prev, cur) in pairwise(X)]
diffs.sort()
print(sum(diffs[:M - N]))


(n, m, *spot) = map(int, open(0).read().split())
spot.sort()
dist = [spot[i + 1] - spot[i] for i in range(m - 1)]
dist.sort(reverse=True)
print(sum(dist[n - 1:]) if dist else 0)


(N, M) = [int(i) for i in input().split()]
X = [int(i) for i in input().split()]
if N >= M:
	print(0)
	return
Xs = sorted(X)
dst = []
for i in range(M - 1):
	dst.append(Xs[i + 1] - Xs[i])
dsts = sorted(dst)
print(sum(dsts[:len(dsts) - N + 1]))


(N, M) = map(int, input().split())
X = sorted(list(map(int, input().split())))
dX = [X[i + 1] - X[i] for i in range(M - 1)]
dX.sort()
p = N - 1
print(sum(dX[:-p]) if p != 0 else sum(dX))


import heapq
(N, M) = list(map(int, input().split()))
X = list(map(int, input().split()))
if N >= M:
	ans = 0
else:
	X.sort()
	distance = [0] * (M - 1)
	for i in range(M - 1):
		distance[i] = -abs(X[i + 1] - X[i])
	sum_distance = sum(distance)
	heapq.heapify(distance)
	count = 0
	for _ in range(N - 1):
		max_num = heapq.heappop(distance)
		count += max_num
	ans = abs(sum_distance - count)
print(ans)


(n, m) = list(map(int, input().split()))
x = list(map(int, input().split()))
x.sort()
dist = [j - i for (i, j) in zip(x, x[1:])]
dist.sort(reverse=1)
print(sum(dist[n - 1:]))


I = lambda : map(int, input().split())
(n, m) = I()
x = sorted(I())
print(sum(sorted((j - i for (i, j) in zip(x, x[1:])))[:max(0, m - n)]))


(n, m) = map(int, input().split())
x_list = [int(i) for i in input().split()]
x_list.sort()
differ_list = []
for i in range(m - 1):
	differ_list.append(x_list[i + 1] - x_list[i])
if n >= m:
	ans = 0
else:
	differ_list.sort(reverse=True)
	ans = sum(differ_list[n - 1:])
print(ans)


f = lambda : map(int, input().split())
(n, m) = f()
l = sorted(f())
d = sorted((l[i] - l[i - 1] for i in range(1, m)))
print(sum(d[:max(0, m - n)]))


(N, M) = list(map(int, input().split()))
X = list(map(int, input().split()))
X.sort()
A = []
for i in range(1, M):
	L = X[i] - X[i - 1]
	A.append(L)
A.sort()
A = A[M - N:]
ans = X[-1] - X[0] - sum(A)
if N >= M:
	ans = 0
print(ans)


(n, m, *a) = map(int, open(0).read().split())
a.sort()
print(abs(sum(sorted([a[s] - a[s + 1] for s in range(m - 1)])[n - 1:])))


(N, M) = map(int, input().split())
x = sorted(list(map(int, input().split())))
ans = []
for i in range(M - 1):
	ans.append(x[i + 1] - x[i])
ans = sorted(ans, reverse=True)
print(sum(ans) - sum(ans[0:N - 1]))


(N, M) = list(map(int, input().split()))
X = list(map(int, input().split()))
X.sort()
subs = []
for i in range(M - 1):
	subs.append(X[i + 1] - X[i])
subs.sort()
if N == 1:
	print(sum(subs))
	return
print(sum(subs[:-(N - 1)]))


(n, m) = map(int, input().split())
X = sorted(map(int, input().split()))
l = sorted([X[i + 1] - X[i] for i in range(m - 1)])
if n == 1:
	print(sum(l))
else:
	print(sum(l[:-n + 1]))


import numpy as np

def main():
	(N, M) = list(map(int, input().split()))
	if N >= M:
		print(0)
		return
	X = sorted(list(map(int, input().split())))
	if N == 1:
		print(X[-1] - X[0])
		return
	D = np.array([X[i + 1] - X[i] for i in range(M - 1)])
	idx_list = np.argsort(-D)[:N - 1]
	ans = sum(D)
	for idx in idx_list:
		ans -= D[idx]
	print(ans)

def __starting_point():
	main()
__starting_point()


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


(n, m, *x) = map(int, open(0).read().split())
x.sort()
d = [i - j for (i, j) in zip(x[1:], x)]
d.sort()
print(sum(d[:m - n]) if n < m else 0)


def solve(N, M, Xi):
	lengthes = []
	Xi.sort()
	for i in range(1, M):
		lengthes.append(abs(Xi[i - 1] - Xi[i]))
	lengthes.sort()
	num = N if N < M else M
	print(sum(lengthes[:M - num]))

def __starting_point():
	(N, M) = list(map(int, input().split()))
	Xi = [int(i) for i in input().split()]
	solve(N, M, Xi)
__starting_point()


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


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


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
y = []
for i in range(1, len(x)):
	y.append(x[i] - x[i - 1])
print(sum(sorted(y, reverse=True)[n - 1:]))


(N, M) = map(int, input().split())
L = sorted(list(map(int, input().split())))
c = sorted([L[i + 1] - L[i] for i in range(M - 1)])[::-1]
print(0 if M <= N else sum(c[N - 1:]))


from fractions import gcd
from itertools import combinations, permutations, accumulate, product
from collections import deque, defaultdict, Counter
import decimal
import re
import math
import bisect
import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
from sys import stdin
readline = stdin.readline

def readInts():
	return list(map(int, readline().split()))

def readTuples():
	return tuple(map(int, readline().split()))

def I():
	return int(readline())
(n, m) = readInts()
A = sorted(readInts())
if n >= m:
	print(0)
else:
	dist = []
	all = 0
	for i in range(m - 1):
		dist.append(A[i + 1] - A[i])
		all += A[i + 1] - A[i]
	dist = sorted(dist, reverse=True)
	print(all - sum(dist[:n - 1]))


(N, M) = map(int, input().split())
N_List = sorted(list(map(int, input().split())))
N_Diff = []
for i in range(1, M):
	N_Diff.append(N_List[i] - N_List[i - 1])
if N >= M:
	ans = 0
elif M == 1:
	ans = sum(N_Diff)
else:
	ans = sum(sorted(N_Diff)[:M - N])
print(ans)


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


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


(n, m) = map(int, input().split())
x = sorted(list(map(int, input().split())))
if n >= m:
	print(0)
else:
	x_dif = sorted([x[i] - x[i - 1] for i in range(1, m)], reverse=True)
	print(x[-1] - x[0] - sum(x_dif[:n - 1]))


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


from itertools import accumulate
import sys

def LI():
	return list(map(int, input().split()))
(N, M) = LI()
X = LI()
if M <= N:
	print(0)
	return
sa = []
X.sort()
for i in range(M - 1):
	sa.append(X[i + 1] - X[i])
sa.sort(reverse=True)
sa = list(accumulate(sa))
if N == 1:
	print(sa[M - 2])
else:
	print(sa[M - 2] - sa[N - 2])


(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X = sorted(X, reverse=False)
if len(X) == 1:
	print(0)
else:
	dist = []
	for i in range(1, M):
		dist.append(X[i] - X[i - 1])
	dist = sorted(dist, reverse=False)
	for k in range(N - 1):
		dist.pop()
		if len(dist) == 0:
			break
	print(sum(dist))


(N, M) = map(int, input().split())
X = sorted(list(map(int, input().split())))
Y = []
for i in range(M - 1):
	y = X[i + 1] - X[i]
	Y.append(y)
y = sorted(Y)[::-1]
print(sum(y[N - 1:]))


(n, m) = map(int, input().split())
l = sorted(list(map(int, input().split())))
s = []
for (i, x) in zip(l, l[1:]):
	s.append(x - i)
ans = l[-1] - l[0]
s.sort(reverse=1)
print(ans - sum(s[:n - 1]))