Problem:


Score : 300 points

Problem Statement

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 1

2 5
10 12 1 2 14

Sample Output 1

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.

Sample Input 2

3 7
-10 -3 0 9 -100 2 17

Sample Output 2

19

Sample Input 3

100 1
-100000

Sample Output 3

0



Sample input:
2 5
10 12 1 2 14


Sample output:
5

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = sorted(map(int, input().split()))
if n >= m:
    print(0)
else:
    dif = []
    for i in range(m-1):
        dif.append(x[i + 1] - x[i])
    dif = sorted(dif)
    for _ in range(n-1):
        dif.pop()
    print(sum(dif))

Submission status: Accepted

Solution code:
N,M= map(int,input().split())
X = list(map(int,input().split()))

if M < N:
    print(0)
    exit()

X = sorted(X)

if N == 1:
    print(X[M-1]-X[0])
    exit()

distance = []
for i in range(M-1):
    distance.append(X[i+1] - X[i])

distance = sorted(distance,reverse=True)

sum = 0
for j in range(N-1):
    sum = sum + distance[j]

print(X[M-1]-X[0]-sum)

Submission status: Accepted

Solution code:
N, M = [int(a) for a in input().split(" ")]
X = sorted([int(a) for a in input().split(" ")])
intervals = sorted([a-b for a, b in zip(X[1:], X[:-1])])[::-1]
if M > N:
    print(sum(intervals) - sum(intervals[:N-1]))
else:
    print(0)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
X = list(map(int,input().split()))

X =sorted(X)

y = []
for i in range(M-1):
    m = X[i+1] - X[i]
    y.append(m)
y = sorted(y)

z = 0
for i in range(len(y)-N+1):
    z += y[i]
print(z)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
X = [int(i) for i in input().split()]
X = sorted(X)

D = [0] * (M-1)
for i in range(len(X)-1):
    D[i] = X[i+1] - X[i]

D = sorted(D, reverse=True)
print(sum(D[N-1:]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

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

x.sort()
diff_x = [x[i] - x[i-1] for i in range(1, len(x))]
diff_x.sort(reverse=True)
ex_diff = diff_x[:N-1]
ans = sum(diff_x) - sum(ex_diff)
if ans > 0:
    print(ans)
else:
    print(0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = sorted(list(map(int, input().split())), reverse=True)

if n>=m or m == 1:
    S =0
else:
    d = sorted([l[i] - l[i+1]  for i in range(m-1)], reverse=True)
    S = max(l) - min(l)
    for i in range(n-1):
        S -= d[i]

print(S)

Submission status: Accepted

Solution code:
import sys
#入力
N, M = map(int, input().split())

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

lst.sort()
#print (lst)

sa = []

for i in range(M-1):
    sa += [abs(lst[i] - lst[i+1])]

sa.sort(reverse = True)
#print(sa)

ans = -(lst[0] - lst[M-1])
#print (ans)
if not sa ==[]:
    if N <= M:
        for j in range(N-1):
            ans -= sa[j]
    else:
        ans = 0
print (ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()


if M == 1:
  print(0)
  exit()

interval = [0] * (M - 1)
for i in range(M-1):
  interval[i] = X[i+1] - X[i]
  
interval.sort()
ans = 0
for i in range(len(interval) - (N-1)):
  ans += interval[i]
  
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()

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

skip = N - 1
print(sum(diffs[skip:]))

Submission status: Accepted

Solution code:

N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
'''
まず一つで考えてみよう
並び替えて、順々に行くのが最適。
方向性を決めることはできるだろうか。
次に二つの場合、どうするか


'''
if len(A) <= N:
    print(0)
    exit(0)

A.sort()
#print(A)
result =[]

for i,a in enumerate(A):
    if i == 0:
        continue
    result.append(A[i]-A[i-1])

result.sort(reverse=True)

print(sum(result[N-1:]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, X: "List[int]"):
    X = sorted(X)
    d = sorted([e - b for b, e in zip(X, X[1:])], reverse=True)
    return X[-1] - X[0] - sum(d[:N-1])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    result = solve(N, M, X)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
N,M = list(map(int,input().split(" ")))
X = list(map(int,input().split(" ")))
X.sort()
diffs = []

if N >= M:
    print(0)
else:
    for i,x in enumerate(X[1:]):
        diff = abs(x-X[i])
        diffs.append(diff)
    diffs.sort()
    # print(diffs)

    if N == 1:
        print(sum(diffs))
    else:
        print(sum(diffs[:-(N-1)]))

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    N, M = list(map(int, input().split()))
    X = list(map(int, input().split()))

    X.sort()
    diffs = []
    for i in range(len(X)-1):
        diffs.append(abs(X[i]-X[i+1]))
    
    diffs.sort()

    ans = 0
    for i in range(len(diffs) - (N-1)):
        ans += diffs[i]
    
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
d = [0]*m
for i in range(1,m):
    d[i] = x[i]-x[i-1]
d.sort()
if n < m:
    d = d[1:m-n+1]
else:
    d = [0]
ans = 0
for i in range(len(d)):
    ans += d[i]
print(ans)

Submission status: Accepted

Solution code:
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:]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

if M > N:
    mvcnt = M - N
    print(sum(xd[:mvcnt]))
else:
    print(0)

Submission status: Accepted

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

X = sorted(X)
Y = [X[i + 1] - X[i] for i in range(M - 1)]
Y = sorted(Y, reverse=True)

ans = sum(Y[(N - 1)::])
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
X = list(map(int, input().split()))
X.sort()

diff = []

if n >= m:
  print(0)
else:
  for i in range(m-1):
    diff.append(abs(X[i]-X[i+1]))
  diff.sort()
  print(max(X)-min(X)-sum(diff[m-n:]))

# 72

Submission status: Accepted

Solution code:
c,n=map(int,input().split())
arr=list(map(int,input().split()))
if c>=n:
  print(0)
else:
  arr=sorted(arr)
  diff=[]
  for i in range(n-1):
    diff.append(abs(arr[i]-arr[i+1]))
  diff=sorted(diff)
  for i in range(c-1):
    diff.pop()
  print(sum(diff))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
L = [0] * (M-1)

for i in range(M-1):
    L[i] = abs(X[i+1] - X[i])

L.sort()

print(sum(L[:-(N-1)]) if N != 1 else sum(L))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
if N >= M:
    print(0)
else:
    diff = []
    for m in range(M-1):
        diff.append(X[m+1] - X[m])
    diff.sort()
    if N == 1:
        print(sum(diff))
    else:
        print(sum(diff[:-(N-1)]))

Submission status: Accepted

Solution code:
r=input().split()
n=int(r[0])
m=int(r[1])

if n<m:
    x=sorted([int(i) for i in input().split()])[::-1]
    xd=sorted([x[i]-x[i+1] for i in range(m-1)])
    if n==1:
        ans=x[0]-x[-1]
    else:
        ans=sum(xd[:-(n-1)])
else:
    ans=0
print(ans)

Submission status: Accepted

Solution code:
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()

print(sum(y[:-n+1]) if n>1 else sum(y))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

X = list(map(int, input().split()))
X.sort()

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x_list=list(map(int,input().split()))
x_list.sort()
d_list=[]
for i in range(0,m-1):
    d_list.append(x_list[i+1]-x_list[i])
if m<=n:
    print(0)
else:
    d_list.sort()
    print(sum(d_list[0:m-n]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

if n >= m:
    print(0)
    sys.exit()
    
l.sort()
le = len(l) - 1
nl = [0] * le
for i in range(0, len(l) - 1):
    nl[i] = l[i + 1] - l[i]
    
nl.sort()
print(sum(nl[:le - n + 1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

NM = list(map(int, input().split()))
X = list(map(int, input().split()))
N = NM[0]
M = NM[1]
#print(X)

if N >= M :
    ans = 0
    print(ans)
    
else:
    Xs = sorted(X)

    #print(Xs)
    length = []
    for i in range(len(Xs)-1):
        length.append(abs(Xs[i+1]-Xs[i]))

    length_n = sorted(length)
    #print(length_n)
    del length_n[M-N:]
    #print(length_n)

    idousum = sum(length_n)

    ans = idousum
    print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())

X=[int(i) for i in input().split()]

X.sort()
X.reverse()

Y=[0]*(M-1)
for j in range(M-1):
    Y[j]=X[j]-X[j+1]

Y.sort()
Y.reverse()

Z=0
for k in range(N-1,M-1):
    Z=Z+Y[k]
print(Z)

Submission status: Accepted

Solution code:
import numpy as np
n,m =map(int, input().split())  #複数数値入力
x=list(map(int, input().split()))  #リスト入力

x.sort()
x_d = list()

if n > m:
    print(0)
else:
    if m == 1:
        print(0)
    else:
#         for i in range(m-1):
#             x_d.append(x[i+1] - x[i])   
        x_d = list(np.diff(x))

#         for i in range(n-1):
            
#             x_d.remove(max(x_d))
            
        x_d.sort(reverse=True)
#         sumd = sum(x_d)  
        sumd = sum(x_d[n-1:])
        print(sumd)

Submission status: Accepted

Solution code:
import numpy as np
import sys
N, M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()

X_list = list(np.diff(X))

if M-N < 1:
    print(0)
    sys.exit()

X_list.sort(reverse=True)
print(sum(X_list[N-1:]))

Submission status: Accepted

Solution code:
n, _  = map(int, input().split())
x = sorted([ int(x) for x in input().split() ])
L = sorted([ x[i+1] - x[i] for i in range(len(x)-1) ], reverse=True )
print(x[-1]-x[0]-sum(L[:n-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
nm = input().split()
n = int(nm[0])
m = int(nm[1])
xlist = [int(x) for x in input().split()]

xlist.sort()

sublist = []
prev_x = None
for x in xlist:
    if prev_x is not None:
        sublist.append(x - prev_x)
    prev_x = x

sublist.sort()

ans = 0
for i in range(max(m - n, 0)):
    ans += sublist[i]

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))

X.sort()
Y = [X[i]-X[i-1] for i in range(1, len(X))]
Y.sort()
if N < M:
    length = len(Y) - N + 1
    print(sum(Y[:length]))
else:
    print(0)

Submission status: Accepted

Solution code:
def solve(n, m, x_list):
    if n >= m:
        return 0

    # time O(M log(M))
    x_list.sort()

    # time O(M)
    diff_list = []
    for key in range(m - 1):
        diff = x_list[key + 1] - x_list[key]
        diff_list.append(diff)

    # time O(M log(M))
    diff_list.sort(reverse=True)

    return sum(diff_list[n-1:])


def main():
    n, m = map(int, input().split())
    x_list = list(map(int, input().split()))

    ans = solve(n, m, x_list)
    print(ans)


main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
X = map(int,input().split(" "))
X = sorted(X)

if N >= M:
    print(0)
    exit()

o = []
for i in range(M-1):
    o.append(X[i+1]-X[i])

ans = X[-1]-X[0]

o.sort(reverse=True)
for i in range(N-1):
    ans -= o[i]

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))

X.sort()

l = []
for i in range(1, len(X)):
  l.append(X[i] - X[i-1])

l.sort(reverse=True)

if len(l) <= N - 1:
    print(0)
else:
    print(sum(l[N-1:]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))

X.sort()
darr = []
for i in range(len(X) - 1):
    darr.append(X[i + 1] - X[i])

darr.sort(reverse=True)
ans = sum(darr[min(N-1, len(darr)):])
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))
if M == 1 or N>=M:
    print(0)
else:
    X.sort()
    X_difs = [X[i+1] - X[i] for i in range(M-1)]
    X_difs.sort()
    for _ in range(N-1):
        X_difs.pop(-1)
    print(sum(X_difs))

Submission status: Accepted

Solution code:
M, N = map(int, input().split())

X = list(map(int, input().split()))
X.sort()

Y = []

for i in range(N - 1):
    Y.append(X[i + 1] - X[i])

Y.sort()

if M < N:
    c = X[-1] - X[0] - sum(Y[N - M:])
else:
    c = 0

print(c)

Submission status: Accepted

Solution code:
M, N = map(int, input().split())

X = list(map(int, input().split()))
X.sort()

Y = []

for i in range(N - 1):
    Y.append((i, X[i + 1] - X[i]))
Y.sort(key=lambda y: y[1], reverse=True)
Y = Y[:M - 1]
Y.sort(key=lambda y: y[0])

p = 0
c = 0
for i, y in Y:
    c += X[i] - X[p]
    p = i + 1
c += X[-1] - X[p]

print(c)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())

if N < M : 

    X = sorted(list(map(int, input().split())))
    
    move = []
    
    for i in range(len(X)-1) : 
        move.append(X[i+1] -X[i])
        
    # print(move)

    move = sorted(move)    

    # print(move)
    
    sum = 0
    
    for i in range(M-N) : 
        sum += move[i]

else : 
    sum = 0
    
print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
S = list(map(int, input().split()))
S.sort()
diff = []

for (i, j) in zip(S, S[1:]):
    diff.append(j-i)

diff.sort(reverse=True)
print(sum(diff[n-1:]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
diff = []

for (i, j) in zip(x, x[1:]):
    diff.append(j-i)

diff.sort(reverse=True)
print(sum(diff[n-1:]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = sorted(list(map(int, input().split())))
diff = []

for (i, j) in zip(x, x[1:]):
    diff.append(j-i)

diff.sort(reverse=True)
print(sum(diff[n-1:]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
xs = list(map(int, input().split()))
xs.sort()
habas = []
for i in range(m - 1):
  habas.append(xs[i+1] - xs[i])
habas.sort()

if n >= m:
  print(0)
else:
  print(sum(habas[:m-n]))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
p = []
for i in range(1,m):
    p.append(X[i]-X[i-1])
p.sort(reverse=True)
#print(p)
print(sum(p[n-1:]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
X=list(map(int,input().split()))

X=sorted(X)

total=abs(X[-1]-X[0])

# 差が大きいところで分割する
gap=[]
for i in range(m-1):
    gap.append(abs(X[i+1]-X[i]))
gap=sorted(gap,reverse=True)

print(total - sum(gap[:n-1]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = [int(i) for i in input().split()]

X.sort()

if M == 1 or N >= M:
    print(0)
    exit()

length = []
for i in range(M-1):
    length.append([abs(X[i+1]-X[i]),i])

length.sort(key=lambda i:i[0], reverse=True)

cand = []
cand.append(0)
for i in range(N-1):
    cand.append(length[i][1]+1)
cand.append(len(X))

anslist = []
for i in range(len(cand)-1):
    anslist.append(X[cand[i+1]-1] - X[cand[i]])

ans = 0
for i in anslist:
    ans += i 

print(ans)

Submission status: Accepted

Solution code:
B = [0]

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
if N >= M: #設置できるコマが座標よりも大きければ終了
    print(0)
    exit()
diff = []
for i in range(1,len(X)):           #座標の差の最大可
    diff.append(X[i]-X[i-1])
diff.sort(reverse=True)
total = sum(diff)
for i in range(N-1):                #移動範囲が広い座標間をショートカット
    total -= diff[i]
print(total)

Submission status: Accepted

Solution code:
from numpy import*
n,m,*x=map(int,open(0).read().split())
x=sorted(x)
x=[x[i+1]-x[i]for i in range(m-1)]
print(int(sum(sorted(x)[::-1][n-1:])))

Submission status: Accepted

Solution code:
import sys
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
if N >= M:
    print(0)
    sys.exit()
X = [int(_) for _ in stdin.readline().rstrip().split()]
X.sort()
diffs = [X[i+1]-X[i] for i in range(M-1)]
diffs.sort()
print(sum(diffs[:M-N]))

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
Xs = list(map(int, input().split()))

if N >= M:
    print(0)
    exit()

Xs_sorted = sorted(Xs)

dists = [Xs_sorted[i+1]-Xs_sorted[i] for i in range(len(Xs_sorted)-1)]
dists_sorted = sorted(dists)

if N == 1:
    print(sum(dists_sorted))
else:
    print(sum(dists_sorted[:-(N-1)]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]

# n: コマ
# x: 目的地 len(x)=M
def main(N, M, Xm):
    # コマ数N >= 目的地数M: クリア
    if N >= M:
        print(0)
        return
    # 目的地は個体区別しないので、簡単のためソート
    Xm.sort()
    # コマ数N == 1: 1コマで端から端まで移動
    if N == 1:
        d = Xm[M-1] - Xm[0]
        print(d)
        return
    # 2 <= コマ数N < 目的地数M: どうする？
    # 発想を変えて、目的地間の距離に注目
    Dm = [Xm[i] - Xm[i-1] for i in range(1, M)]
    # 区間は、間隔が短い順に並ぶとする
    Dm.sort()
    # 全てのコマの移動方向は右とする
    # コマ1は一番左の目的地からスタート
    # コマ2～Nは右端の目的地から埋めていく
    # 1             5     4      3       2      コマ
    # x-x--x---x----x-----x------x-------x      目的地（区間が短い順）
    # あとは、コマ1が、コマNの隣まで進めばよい、その距離が答えとなる
    d = 0
    for i in range(M-N):
        d += Dm[i]
    print(d)

N, M = i2nn()
Xm = i2nn()
main(N, M, Xm)

"""
C - Streamline
https://atcoder.jp/contests/abc117/tasks/abc117_c

2 5
10 12 1 2 14
    5

3 7
-10 -3 0 9 -100 2 17
    19

100 1
-100000
    0
"""

Submission status: Accepted

Solution code:
import numpy as np
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
a = np.array(a)

diff = a[:-1] - a[1:]
diff.sort()

if n == 1:
    print(sum(diff))
else:
    print(sum(diff[:-n + 1]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
if N >= M:
    print(0)
    exit()
diff = []
for i in range(1, len(X)):
    diff.append(X[i]-X[i-1])
diff.sort(reverse=True)
total = sum(diff)
for i in range(N-1):
    total -= diff[i]
print(total)

Submission status: Accepted

Solution code:
N,M =map(int,input().split(' '))
X = sorted(list(map(int,input().split(' '))))

Y = sorted([n- X[i-1] for i, n in enumerate(X) if i != 0], reverse=True)

print(X[M-1] - X[0] - sum(Y[0:N-1]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()

if n >= m:
    print(0)
    exit()
    
sub = [0]*(m-1)
for i in range(m-1):
    sub[i] = x[i+1] - x[i]
sub.sort()

ass = 0
for i in range(m-n):
    ass += sub[i]
print(ass)

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
X = sorted(list(map(int, input().split())))
div = [0]*(M-1)
for i in range(M-1):
    div[i] = abs(X[i+1] - X[i])
div = sorted(div,reverse=True)
ans = X[-1] - X[0]
if N >= M:
    print(0)
    sys.exit(0)
ans -= sum(div[:N-1])
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
#if N >= M:
#  print(0)
#  exit()
  
X = list(map(int,input().split()))

X.sort()
diff = []

for i in range(1,M):
  diff.append(X[i]-X[i - 1])

diff.sort()

for i in range(N - 1):
  if len(diff) != 0:
    diff.pop()

print(sum(diff))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
X = [int(i) for i in input().split()]

X.sort()

maxlist = [0] * (M-1)
cnt = 0
ans = 0

for i in range(1,M):
    maxlist[i-1]= X[i] - X[i-1]
    ans += maxlist[i-1]
    
maxlist.sort()
maxlist.reverse()

minus = 0
for i in range(min(N,M)-1):
    minus += maxlist[i]
    
print(ans-minus)

Submission status: Accepted

Solution code:
n, m = map(int, (input().split()))
x = sorted(list(map(int, input().split())))
y = sorted([i - x[n - 1]  for n ,i in enumerate(x) if n != 0], reverse=True)
print(sum(y[n - 1:]))

Submission status: Accepted

Solution code:
N,M=[int(i) for i in input().split()]
X=[int(i) for i in input().split()]
X.sort()
rui=[]
for i in range(len(X)-1):
  rui.append(X[i+1]-X[i])
rui.sort()
if N==1:
  print(sum(rui))
elif M>=N:
  print(sum(rui[0:-(N-1)]))
else:
  print(0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))

if M <= N:
    ans = 0
else:
    points = X[:]
    points.sort()

    diff_p = []
    for i in range(1, len(points)):
        diff_p.append(points[i] - points[i-1])

    diff_p.sort()
    #print(diff_p)

    ans = sum(diff_p[:M-N])
print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
N, M = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
diff = [abs(x[i] - x[i+1]) for i in range(M-1)]
diff.sort()
ans = 0
print(ans if N > M else ans + sum(diff[:M-N]))

Submission status: Accepted

Solution code:
n,m = [int(i) for i in input().split()]
x = list(map(int, input().split()))

score = max(x) - min(x)

x.sort()

dist = []

for i in range(1,m):
    dif = x[i] - x[i-1]
    dist.append(dif)

dist.sort()

#distはながさm-1

if n >= m:
    score = 0
else:
    for i in range(1,n):
        reduce = dist[-i]
        score -= reduce
print(score)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
if N>=M:
    print(0)
    exit()
X=[int(i) for i in input().split()]
X.sort()
Y=[X[i+1]-X[i] for i in range(M-1)]
Y.sort()
ans=0
for i in range(M-N):
    ans+=Y[i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
X = list(map(int,input().split()))

X.sort()
if N>=M:
    print(0)
else:
    tmp=[]
    for i in range(M-1):
        tmp.append(X[i+1] - X[i])
    tmp.sort(reverse = True)
    interval = 0
    for i in range(N-1):
        if i+1 == M-1:
            break
        interval += tmp[i]
    print(sum(tmp) - interval)

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
x = map(int, raw_input().split())

if n >= m:
    print 0
else:
    x.sort()
    l = []
    for i in range(m - 1):
        l.append(x[i + 1] - x[i])
    l.sort(reverse=True)
    sum = sum(l[:n - 1])
    print x[m - 1] - x[0] - sum

Submission status: Accepted

Solution code:
N, M = map(int, input().split(" "))
Xs = map(int, input().split(" "))

X_lst = sorted(Xs)
dX = sorted([X_lst[i+1] - X_lst[i] for i in range(len(X_lst)-1)])
if N >= M:
  print(0)
elif N == 1:
  print(sum(dX))
else:
  print(sum(dX[:-(N-1)]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
if N >= M:
    print(0)
else:
    tmp = []
    for i in range(M - 1):
        tmp.append(A[i+1] - A[i])
    tmp.sort(reverse=True)
    interval = 0
    for i in range(N - 1):
        if i + 1 == M - 1:
            break
        interval += tmp[i]
    print(sum(tmp) - interval)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
zahyo = list(map(int, input().split()))
zahyo.sort()
sa = [0 for _ in range(M-1)]

for i in range(M-1):
    sa[i] = zahyo[i+1] - zahyo[i]

sa.sort(reverse=True)
sa = sa[N-1:]

print(sum(sa))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, X: "List[int]"):
    if N >= M:
        print(0)
        return
    X.sort()
    dist = []
    for i in range(1, len(X)):
        dist.append(abs(X[i] - X[i - 1]))
    distIndices = [(dist[i], i) for i in range(len(dist))]
    distIndices.sort(reverse=True)
    splitIndex = []
    for i in range(N-1):
        splitIndex.append(distIndices[i][1])
    splitIndex.sort()
    ranges = []
    begin = 0
    for next in splitIndex:
        ranges.append(X[begin:next+1])
        begin = next+1
    ranges.append(X[begin:])
    cost = 0
    for R in ranges:
        if len(R) == 1:
            continue
        cost += R[-1] - R[0]
    print(cost)
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, X)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

dif = []
for i in range(M-1):
    dif.append(A[i+1] - A[i])

dif.sort(reverse=True)
dif = dif[N-1:]

print(sum(dif))

Submission status: Accepted

Solution code:
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g


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

for i in range(m-n):
    ans += temp[i]
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
X = sorted(list(map(int, input().split())))

if N >= M:
    print(0)
    exit()

path_cnt = sorted([X[i + 1] - X[i] for i in range(M - 1)])
if N == 1:
    print(sum(path_cnt))
else:
    print(sum(path_cnt[:-N + 1]))

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
X = [int(i) for i in input().split()]

if N >= M:
    print(0)
    exit()


X.sort()
L = [X[i+1] - X[i] for i in range(len(X)-1)]
L.sort()

print(sum(L[:(M-N)]))