Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

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

dp = [float("inf")]*n
dp[0]=0
for i in range(n-1):
    for j in range(1,k+1):
        if i+j<n:
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
print(dp[n-1])

### FIXED CODE ###

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

dp = [float("inf")]*n
dp[0]=0
for i in range(n-1):
    for j in range(1,k+1):
        if i+j<n:
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
print(dp[n-1])
### BUGGY CODE ###

l = list(map(int,input().split()))
a = l[0]
b = l[1]
n = l[2]

def floor(a,b,x):
    p = (a*x)//b - a*(x//b)
    return p

max = 0
if n < b-1:
    max = floor(a,b,n)
else:
    for i in range(b-1,n+1,b):
        c = floor(a,b,i)
        if c >= max:
            max = c

print(max)

### FIXED CODE ###

l = list(map(int,input().split()))
a = l[0]
b = l[1]
n = l[2]

def floor(a,b,x):
    p = (a*x)//b - a*(x//b)
    return p

max = 0
if b == 1:
    max = 0
elif n <= b-1:
    max = floor(a,b,n)
elif n > b-1:
    for i in range(b-1,n+1,b):
        c = floor(a,b,i)
        if c >= max:
            max = c

print(max)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import re, sys

s = input()

regex = re.compile(r'(dream|dreamer|erase|eraser)$')

while(len(s)):
	if re.search(regex, s):
		s = re.sub(regex, '', s)
	else:
		print('NO')
		sys.exit()

print('YES')

### FIXED CODE ###

# -*- coding: utf-8 -*-
import re, sys

s = input()

regex = re.compile(r'^(dream|dreamer|erase|eraser)+$')

result = 'YES' if re.search(regex, s) else 'NO'
print(result)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**6)
n,q=[int(i) for i in input().split()]
ki=[[] for _ in range(n)]
ans=[0]*n

def dfs(numQ,parent):
    for child in ki[numQ]:
        if child!=parent:
            ans[child]+=ans[numQ]
            dfs(child,numQ)

for i in range(n-1):
    a,b=[int(_) for _ in input().split()]
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)

for i in range(q):
    p,x=[int(_) for _ in input().split()]
    ans[p-1]+=x

dfs(0,-1)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n,q=map(int,input().split())
ki=[[] for _ in range(n)]
ans=[0]*n

def dfs(numQ,parent):
    for child in ki[numQ]:
        if child==parent:
            continue
        ans[child]+=ans[numQ]
        dfs(child,numQ)

for i in range(n-1):
    a,b=map(int,input().split())
    ki[a-1].append(b-1)
    ki[b-1].append(a-1)

for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x

dfs(0,-1)
print(*ans)
### BUGGY CODE ###

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

for i in range(n):
    if len([ a for a in l if  l[0] -1 > a]) > 0:
        print('No')
        sys.exit()
    else:
        l = l[i::]
print('Yes')


### FIXED CODE ###

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

max = l[0]
for i in range(n):
    if max - 1 > l[i]:
        print('No')
        sys.exit()
    elif l[i] > max:
        max = l[i]
print('Yes')
### BUGGY CODE ###

n = int(input())
list = []

for ni in range(1,n+1):
    if ni ** 2 <= n:
        if n % ni == 0:
            list.append(max(len(str(ni)),len(str(n//ni))))
print(min(list))

### FIXED CODE ###

#abc057c
n = int(input())
list = []

for ni in range(1,n+1):
    if ni * ni <= n:
        if n % ni == 0:
            list.append(max(len(str(ni)),len(str(n//ni))))
    else:
        break
print(min(list))
### BUGGY CODE ###

n, m = map(int, input().split())
dat_m = [[]] * (n+1)
dat_finish = [False] * (n+1)


for i in range(m):
    a,b = map(int, input().split())
    dat_m[a] = dat_m[a] + [b]
    if b == n:
        dat_finish[a] = True
#print(dat_m)
#print(dat_finish)

c = False
for i in dat_m[1]:
    if dat_finish[i]:
        c = True
print("POSSIBLE" if c else "IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
dat = []
dat_m = [[]] * (n+1)
dat_finish = [False] * (n+1)

for i in range(m):
    a,b = map(int, input().split())
    dat.append( (a,b) )

#print(dat)
for i in range(m):
    a,b = dat[i]
    if b == n:
        dat_finish[a] = True
#print(dat_finish)

c = False
for i in range(m):
    a,b = dat[i]
    if a == 1:
        if dat_finish[b]:
            c = True

print("POSSIBLE" if c else "IMPOSSIBLE")
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
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 main():
    n,m = LI()
    a = sorted(LI())
    aa = sorted([LI() for _ in range(m)], key=lambda x: -x[1])
    ai = 0
    for b,c in aa:
        for j in range(b):
            if ai >= n:
                break
            if a[ai] < c:
                a[ai] = c
                ai += 1
        if ai >= n:
            break

    return sum(a)


print(main())



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
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 main():
    n,m = LI()
    a = sorted(LI())
    aa = sorted([LI() for _ in range(m)], key=lambda x: -x[1])
    ai = 0
    for b,c in aa:
        for j in range(b):
            if ai >= n:
                break
            if a[ai] < c:
                a[ai] = c
                ai += 1
            else:
                break
        if ai >= n:
            break

    return sum(a)


print(main())
### BUGGY CODE ###

n,w=map(int,input().split())

weight=[]
value=[]
for i in range(n):
  a,b=map(int,input().split())
  weight.append(a)
  value.append(b)

  
dp=[[float('inf')]*(sum(value)+1) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
  for j in range(sum(value)+1):
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])
    dp[i+1][min(j+value[i],sum(value))]=min(dp[i+1][min(j+value[i],sum(value))],dp[i][j]+weight[i])

ans=0
for i in range(sum(value)+1):
  if dp[-1][i]<=w:
    ans=max(ans,i)

print(ans)


### FIXED CODE ###

n,w=map(int,input().split())

weight=[]
value=[]
for i in range(n):
  a,b=map(int,input().split())
  weight.append(a)
  value.append(b)

xxx=sum(value)
dp=[[float('inf')]*(sum(value)+1) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
  for j in range(xxx+1):
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])                             #+1、個数制限なし
    dp[i+1][min(j+value[i],xxx)]=min(dp[i+1][min(j+value[i],xxx)],dp[i][j]+weight[i])

ans=0
for i in range(xxx+1):
  if dp[-1][i]<=w:
    ans=max(ans,i)

print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())

a = []

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            a.append(x+y+z)


print(a.count(s))

### FIXED CODE ###

k,s=map(int,input().split())
print(len([1 for z in range(k+1) for y in range(k+1) if 0<=s-y-z<=k]))
### BUGGY CODE ###

#060_D
n, w_ = map(int, input().split())
w, v = [], []

for _ in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
    
dp = [[0 for _ in range(w_+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, w_+1):
        if j < w[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])

print(dp[n][w_])

### FIXED CODE ###

#060_D
n, W = map(int, input().split())
w1, w2, w3, w4 = [], [], [], []
w, v = map(int, input().split())
w1.append(v)
for _ in range(n-1):
    a, b = map(int, input().split())
    if a == w: w1.append(b)
    if a == w+1: w2.append(b)
    if a == w+2: w3.append(b)
    if a == w+3: w4.append(b)
    
for w_ in [w1, w2, w3, w4]:
    w_.sort(reverse= True)
    
ans = 0
for i in range(0, len(w1)+1):
    for j in range(0, len(w2)+1):
        for k in range(0, len(w3)+1):
            res = W - (i * w + j * (w+1) + k * (w+2))
            if res < 0:
                continue
            tmp = sum(w1[:i])+sum(w2[:j])+sum(w3[:k])+sum(w4[:res//(w+3)])
            ans = max(tmp, ans)
            
print(ans)
### BUGGY CODE ###


N=int(input())
A = []
for n in range(N):
    A.append(int(input()))

forward = [0 for n in range(N)]
forward[0] = A[0]
backward = [0 for n in range(N)]
backward[N-1] = A[N-1]
for n in range(1,N):
    forward[n] = max(forward[n-1], A[n])
for n in range(N-1)[::-1]:
    backward[n] = max(backward[n+1], A[n])

# print(forward)
# print(backward)

for n in range(N):
    # print("====")
    # print(forward[:n])
    # print(backward[n+1:])
    print(max(forward[:n]+backward[n+1:]))


### FIXED CODE ###


N=int(input())
A = []
for n in range(N):
    A.append(int(input()))

forward = [0 for n in range(N)]
forward[0] = A[0]
backward = [0 for n in range(N)]
backward[N-1] = A[N-1]
for n in range(1,N):
    forward[n] = max(forward[n-1], A[n])
for n in range(N-1)[::-1]:
    backward[n] = max(backward[n+1], A[n])

# print(forward)
# print(backward)

print(backward[1])
for n in range(1,N-1):
    # print("====")
    # print(forward[n-1],backward[n+1])
    print(max(forward[n-1],backward[n+1]))
print(forward[N-2])
### BUGGY CODE ###

n = int(input())
a = [input() for _ in range(n)]

a_dict = {i:0 for i in set(a)}
a_list = list(set(a))

for i in a_list:
    a_dict[i] = a.count(i)

ans = []
max_value = max(a_dict.values())
for key, value in a_dict.items():
    if value == max_value:
        ans.append(key)

ans.sort()
for i in ans:
    print(i)

### FIXED CODE ###

n = int(input())

# 入力データ受取り時に、辞書に追加していくやり方
s_dict = {}
for i in range(n):
    s = input()    
    if s not in s_dict:
        s_dict[s] = 1
    s_dict[s] += 1

max_value = max(s_dict.values())
ans = []
for key, value in s_dict.items():
    if value == max_value:
        ans.append(key)

ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

import sys
import numpy as np
import math
# for AtCoder
# import fractions
from collections import deque 
from functools import reduce
from functools import lru_cache

# input = sys.stdin.readline

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n = int(input())

sum = 0

for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            sum += gcd_list([i, j, k])
print(sum)            

### FIXED CODE ###

import sys
import numpy as np
import math

from collections import deque 
from functools import reduce
from functools import lru_cache

# input = sys.stdin.readline

n = int(input())

gcd_num = 0

for i in range(1, n+1):
    for j in range(1, n+1):
        g = math.gcd(i, j)
        for k in range(1, n+1):
            gcd_num += math.gcd(g, k)
print(gcd_num)
### BUGGY CODE ###

S=list(str((input())))
Q=int(input())
for i in range(Q):
    T=list(map(str,input().split()))
    if T[0]=="1":
        S.reverse()
    if T[0]=="2":
        if T[1]=="1":
            S.insert(0,T[2])
        if T[1]=="2":
            S.append(T[2])

print("".join(S))

### FIXED CODE ###

from collections import deque

S=deque(str((input())))
Q=int(input())
t=0
for _ in range(Q):
    T=list(map(str,input().split()))
    if T[0]=="1":
        t+=1
    else:
        if (T[1]=="1" and t%2 == 0) or (T[1]=="2" and t%2 != 0):
            S.appendleft(T[2])
        else:
            S.append(T[2])


if t%2 != 0:
    S.reverse()

print("".join(S))
### BUGGY CODE ###

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    visit = [False]*n
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        if visit[j]:
            if a[j] != b[j]:
                print(-1)
                return 0
            visit[j-1] = True
            visit[jj] = True
            continue
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if a[j] != b[j]:
                print(-1)
                return 0
            visit[j-1] = True
            visit[jj] = True
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)


main()


### FIXED CODE ###

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if temp:
                print(-1)
                return 0
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)
main()
### BUGGY CODE ###

from collections import Counter
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    lis = list(map(int,input().split()))
    ans = Counter(lis)
    for j in range(n):
        su = 0
        for k, v in ans.items():
            if k == lis[j]:
                su += (v - 2) * (v - 1) // 2
            else:
                su += (v - 1) * v // 2
        print(su)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    lis = list(map(int,input().split()))
    d = Counter(lis)
    su = 0
    for e in d:
        su += (d[e] - 1) * d[e] // 2

    for e in lis:
        if d[e] <= 1:
            print(su)
        else:
            k = d[e]
            res = su - k*(k-1)//2 + (k-1)*(k-2)//2
            print(res)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

#b
n = int(input())
s = [input() for _ in range(n)]
s.sort(key=len)
ans = 0
trie = {'!': True}
for si in s:
    cursor = trie
    si = list(si)
    while True:
        for nextchar in cursor:
            if nextchar == '!':
                continue
            if '!' in cursor[nextchar] and nextchar in si:
                ans += 1
        popchar = si.pop(-1)
        if popchar in cursor:
            cursor = cursor[popchar]
        else:
            cursor[popchar] = {}
            cursor = cursor[popchar]
            for popchar in reversed(si):
                cursor[popchar] = {}
                cursor = cursor[popchar]
            cursor['!'] = True
            break
print(ans)

### FIXED CODE ###

#b（直し）
class TrieNode:
    def __init__(self):
        self.parent = None
        self.children = {}
    def new_child(self, key):
        self.children[key] = TrieNode()
        self.children[key].parent = self
        self.children[key].label = key
        return self.children[key]

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

n = int(input())
s = [input() for _ in range(n)]
ans = -n # (Si, Si)
trie = TrieNode()
ends = set()

#build the trie
for si in s:
    cursor = trie
    for char in reversed(si):
        if char in cursor.children:
            cursor = cursor.children[char]
        else:
            cursor = cursor.new_child(char)
    else:
        ends.add(cursor)

#climb up the trie
for cursor in ends:
    head = set()
    while cursor.parent is not None:
        head.add(cursor.label)
        cursor = cursor.parent
        for char in cursor.children:
            if cursor.children[char] in ends and char in head:
                ans += 1
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    D = tuple(map(int, input().split()))
    M = int(input())
    T = tuple(map(int, input().split()))

    problem = dict()
    for i in D:
        problem[i] = problem.get(i, 0) + 1

    for i in T:
        if i in D:
            problem[i] -= 1
            if problem[i] < 0:
                ans = 'NO'
                break
        else:
            ans = 'NO'
            break
    else:
        ans = 'YES'

    print(ans)

main()


### FIXED CODE ###

def main():
    N = int(input())
    D = tuple(map(int, input().split()))
    M = int(input())
    T = tuple(map(int, input().split()))

    d = dict()
    for i in D:
        d[i] = d.get(i, 0) + 1

    t = dict()
    for i in T:
        t[i] = t.get(i, 0) + 1

    for key, val in t.items():
        if key in d.keys():
            d[key] -= val
            if d[key] < 0:
                ans = 'NO'
                break
        else:
            ans = 'NO'
            break
    else:
        ans = 'YES'

    print(ans)

main()
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[26]:


N = int(input())
A = sorted(list(map(int, input().split())))


# In[27]:


ans = 1
asm = [sum(A[:i+1]) for i in range(N)]
for i in range(2,N+1):
    if asm[-i]*2 >= A[-i+1]:
        ans += 1
    else:
        break
print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[26]:


N = int(input())
A = sorted(list(map(int, input().split())))


# In[32]:


tmp = 0
asm = []
for i in range(N):
    tmp += A[i]
    asm += [tmp]
ans = 1
for i in range(2,N+1):
    if asm[-i]*2 >= A[-i+1]:
        ans += 1
    else:
        break
print(ans)


# In[ ]:
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)
max_v = N*sum(v)
dp = [INF]*(max_v+1)
dp[0] = 0
for w, v in zip(w, v):
	for i in range(max_v, -1, -1):
		if i-v >= 0:
			dp[i] = min(dp[i], dp[i-v]+w)

ans = 0
for i in range(len(dp)):
	if dp[i] <= W:
		ans = i
print(ans)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)
max_v = sum(v)
dp = [INF]*(max_v+1)
dp[0] = 0
for w, v in zip(w, v):
	for i in range(max_v, -1, -1):
		if i-v >= 0:
			dp[i] = min(dp[i], dp[i-v]+w)

ans = 0
for i in range(len(dp)):
	if dp[i] <= W:
		ans = i
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j >= wv[i][0]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j >= wv[i][0]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[N][W])
### BUGGY CODE ###

import sys
 
 
n, x, y = map(int, sys.stdin.readline().split())
dist = []
for i in range(n):
    dist.append([])
    for j in range(n):
        dist[i].append(abs(j - i))
 
dist[x-1][y-1] = 1
def get_dist(a,b):
    if a < b:
        return dist[a][b]
    else:
        return dist[b][a]
 
for k in range(n):
    for i in range(n-1):
        for j in range(i+1, n):
            dist[i][j] = min(dist[i][j], get_dist(i, k) + get_dist(k, j))
 
final = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1, n):
        final[dist[i][j]-1] += 1
 
for one in final:
    print(one)

### FIXED CODE ###

import sys
n, x, y = map(int, sys.stdin.readline().split())

x -= 1
y -= 1
    
final = [0]*(n-1)


for i in range(n-1):
    for j in range(i+2, n):
        if j < x or i > y:
            dist = j-i
        else:
            dist = min([j - i, abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)])
        final[dist-1] += 1 
final[0] = n
res = [str(one) for one in final]
print ("\n".join(res))
### BUGGY CODE ###

import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    #n = int(stdin.readline().rstrip())
    n,m = map(int, stdin.readline().rstrip().split())
    x = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    if n>m:
        print(0)
        exit()
    spl = n-1
    sa = []
    x.sort()
    for i in range(m-1):
        sa.append(x[i+1] - x[i])
    for i in range(spl):
        sa.pop(sa.index(max(sa)))
    print(sum(sa))



main()


### FIXED CODE ###

import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    #n = int(stdin.readline().rstrip())
    n,m = map(int, stdin.readline().rstrip().split())
    x = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    if n>m:
        print(0)
        exit()
    spl = n-1
    sa = [0]*(m-1)
    x.sort()
    for i in range(m-1):
        sa[i] = x[i+1] - x[i]
    sa.sort()
    i = m-n
    print(sum(sa[:i]))



main()