Harryxun/stf_run huggingface dataset:
n = int(input())
a = list(map(int,input().split()))
g = [[]for i in range(n)]
for i in range(n-1):
  x,y = map(int,input().split())
  x-=1;y-=1
  g[x].append(y)
  g[y].append(x)
used = [0]*n
ue = [0]*n
for i in range(n):
  if len(g[i])== 1:
    ne = i
    break
huka = [0]*n
def dfs(x,y,z):
  if used[x]:
    return 0
  used[x] = 1
  huka[x] = y
  ue[x] = z
  for ix in g[x]:
    dfs(ix,y+1,x)
dfs(ne,0,-1)
for i in range(n):
  huka[i] = [huka[i],i]
huka.sort(key=lambda x:-x[0])
hen = [0]*(n)
for i in range(n-1):
  x = huka[i][1]
  if len(g[x]) == 1:
    hen[x] = a[x]
    hen[ue[x]] += hen[x]
    if hen[x] > a[ue[x]]:
      print("NO")
      exit()
    continue
  hen[x] = a[x]*2-hen[x]
  hen[ue[x]] += hen[x]
  if hen[x] > a[ue[x]]:
    print("NO")
    exit()
  if hen[x] <0:
    print("NO")
    exit()
if hen[ne] != a[ne]:
  print("NO")
else:
  print("YES")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
a = list(map(int,input().split()))
g = [[]for i in range(n)]
for i in range(n-1):
  x,y = map(int,input().split())
  x-=1;y-=1
  g[x].append(y)
  g[y].append(x)
used = [0]*n
ue = [0]*n
for i in range(n):
  if len(g[i])== 1:
    ne = i
    break
huka = [0]*n
def dfs(x,y,z):
  if used[x]:
    return 0
  used[x] = 1
  huka[x] = y
  ue[x] = z
  for ix in g[x]:
    dfs(ix,y+1,x)
dfs(ne,0,-1)
for i in range(n):
  huka[i] = [huka[i],i]
huka.sort(key=lambda x:-x[0])
hen = [0]*(n)
for i in range(n-1):
  x = huka[i][1]
  if len(g[x]) == 1:
    hen[x] = a[x]
    hen[ue[x]] += hen[x]
    if hen[x] > a[ue[x]]:
      print("NO")
      exit()
    continue
  hen[x] = a[x]*2-hen[x]
  hen[ue[x]] += hen[x]
  if hen[x] > a[ue[x]] or hen[x]>a[x]:
    print("NO")
    exit()
  if hen[x] <0:
    print("NO")
    exit()
if hen[ne] != a[ne]:
  print("NO")
else:
  print("YES")
def insertionSort( nums, n, g ):
    global cnt
    for i in range( g, n ):
        v = nums[i]
        j = i - g
        while ( 0 <= j ) and ( v < nums[j] ):
            nums[ j+g ] = nums[j]
            j -= g
            cnt += 1
        nums[ j+g ] = v
 
def shellSort( nums ):
    global cnt
    g = []
    v = 1
    n = len( nums )
    while v <= n:
        g.append( v )
        v = 3*v+1     
    g.reverse( )
    m = len( g )
    print( m )
    print( " ".join( map( str, g ) ) )  
    cnt = 0
    for i in range( m ):
        insertionSort( nums, n, g[i] )
    print( cnt )
    print( "\n".join( map( str, nums ) ) )
 
n = int( input( ) )
nums = [ int( input( ) ) for i in range( n ) ]
shellSort( nums )

### FIXED CODE ###

import sys
 
def insertionSort( nums, n, g ):
    cnt = 0
    i = g
    while i < n:
        v = nums[i]
        j = i - g
        while 0 <= j and v < nums[j]:
            nums[ j+g ] = nums[j]
            j -= g
            cnt += 1
        nums[ j+g ] = v
        i += 1
    return cnt
         
def shellSort( nums, n ):
    g = []
    val = 1
    while val <= n:
        g.append( val )
        val = 3*val+1
     
    g.reverse( )
    m = len( g )
    print( m )
    print( " ".join( map( str, g ) ) )
    cnt = 0
    for i in range( m ):
        cnt += insertionSort( nums, n, g[i] )
    print( cnt )
     
n = int( sys.stdin.readline( ) )
nums = []
for i in range( n ):
    nums.append( int( sys.stdin.readline( ) ) )
 
shellSort( nums, n )
print( "\n".join( map( str, nums ) ) )
import sys
sys.setrecursionimit(200000)
n,l=map(int,input().split())
r=list(map(int,input().split()))
last=0;tiepoint=0
for i in range(n-1):
  if r[i]+r[i+1]>last:
    last=r[i]+r[i+1]
    tiepoint=i
if last>=l:
  print("Possible")
  for i in range(tiepoint-1):
    print(i+1)
  for i in range(tiepoint+1,n)[::-1]:
      print(i+1)
  print(tiepoint+1)
else:print("Impossible")


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
n,l=map(int,input().split())
r=list(map(int,input().split()))
last=0;tiepoint=0
for i in range(n-1):
  if r[i]+r[i+1]>last:
    last=r[i]+r[i+1]
    tiepoint=i
if last>=l:
  print("Possible")
  for i in range(tiepoint):
    print(i+1)
  for i in range(tiepoint+1,n-1)[::-1]:
      print(i+1)
  print(tiepoint+1)
else:print("Impossible")
x1, y1, x2, y2 = map(int, input().split())
x = x1 - x2
y = y1 - y2
point3 = [x2 + y, y2 - x]
point4 = [x1 + y, y1 - x]
print(*[*point3, *point4], sep=' ')


### FIXED CODE ###

x1, y1, x2, y2 = map(int, input().split())
x = x1 - x2
y = y1 - y2
point3 = [x2 + y, y2 - x]
point4 = [x1 + y, y1 - x]
print(*[point3[0], point3[1], point4[0], point4[1]], sep=' ')
a = int(input())
s, t = map(str, input().split())
a, b = map(int, input().split())
u = input()
if u=s a-=1
if u=t b-=1
print(a b)

### FIXED CODE ###

s, t = map(str, input().split())
a, b = map(int, input().split())
u = input()
if u==s:
    a-=1
if u==t:
    b-=1
print(a,b)
N = int(input())
total = 0
for i in range(1,N+1):
	if i%3!=0 and i%5!=0:
    	total += i
print(total)

### FIXED CODE ###

N = int(input())
total = 0
for i in range(1, N+1):
    if (i % 3) != 0 and (i % 5) != 0:
        total = total+i
print(total)
S = input()
N = len(S)

D = [0 for i in range(26)]
for i in range(N):
    D[ord(S[i]) - 97] = 1

if N != 26:
    for i in range(N):
        if D[i] == 0:
            s = chr(97 + i)
            break
    print(S + s)

else:
    if S == "abcdefghijklmnopqrstuvwxyz"[::-1]:
        print(-1)
    else:
        c = 2
        for i in range(N):
            if ord(S[-2 - i]) - ord(S[-1 - i]) == 1:
                c += 1
            else:
                break
        print(S[:26 - c] + S[-1])


### FIXED CODE ###

S = input()
N = len(S)

D = [0 for i in range(26)]
for i in range(N):
    D[ord(S[i]) - 97] = 1

if N != 26:
    for i in range(26):
        if D[i] == 0:
            s = chr(97 + i)
            break
    print(S + s)

else:
    if S == "abcdefghijklmnopqrstuvwxyz"[::-1]:
        print(-1)
    else:
        c = 2
        for i in range(N):
            if ord(S[-2 - i]) - ord(S[-1 - i]) >= 1:
                c += 1
            else:
                break
        s = sorted(list(S[26 - c:]))
        for i in s:
            if ord(i) > ord(S[-c]):
                key = i
                break

        print(S[:26 - c] + key)
print(2**int(input))

### FIXED CODE ###

n=int(input())
print(n**3)
import heapq
x, y, z, k = map(int, input().split())
n = [x, y, z]
if x*y*z < k:
    k = x*y*z

abc = []
for _ in range(3):
    *l, = sorted(map(int, input().split()), reverse=True)
    abc.append(l)

h = [[-(abc[0][0]+abc[1][0]+abc[2][0]), [0, 0, 0]]]
heapq.heapify(h)

index = [0, 0, 0]
se = h[:]

for _ in range(k):
    ans, iterate = heapq.heappop(h)
    print(-ans)

    for i in range(3):
        if n[i] <= iterate[i] + 1: continue

        iterate[i] += 1

        s = -(abc[0][iterate[0]]+abc[1][iterate[1]]+abc[2][iterate[2]])
        t = [s, iterate[:]]

        if t not in se:
            heapq.heappush(h, t)
            se.append(t)

        iterate[i] -= 1


### FIXED CODE ###

x, y, z, k = map(int, input().split())
*a, = sorted(map(int, input().split()), reverse=True)
*b, = sorted(map(int, input().split()), reverse=True)
*c, = sorted(map(int, input().split()), reverse=True)

ab = [a[i] + b[j] for j in range(y) for i in range(x)]
ab.sort(reverse=True)
ab = ab[:k]

abc = [ab[i] + c[j] for j in range(z) for i in range(len(ab))]

abc.sort(reverse=True)

for i in range(k):
    print(abc[i])
n,W=map(int,input().split())
wv=[[int(j) for j in input().split()] for i in range(n)]
dp=[[0]*110 for i in range(110000)]

for i in range(1,n+1):
  for j in range(W+1):
    dp[i][j]=dp[i-1][j]
    if j-wv[i-1][0]>=0:
      dp[i][j]=max(dp[i][j],
                   dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
      
print(dp[n][W])

### FIXED CODE ###

N,W=map(int,input().split())
L = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for j in range(110000)] for i in range(110)]
for i in range(1,N+1):
  for j in range(W+1):
    dp[i][j]=dp[i-1][j]
    if j-L[i-1][0]>=0:
      dp[i][j]=max(dp[i][j],dp[i-1][j-L[i-1][0]]+L[i-1][1])
ans=dp[N][W]
print(ans)
import math

N = int(input())
A = [int(x) for x in input().split()]

left = [0] * (N+1)
right = [0] *(N+1)

for i in range(N):
    left[i+1] = math.gcd(left[i], A[i])
for i in reversed(range(N)):
    right[i] = math.gcd(right[i+1], A[i])
    
res = 0
for i in range(N):
    l = left[i]
    r = right[i+1]
    res = max(math.gcd(l, r), res)

print(res)

### FIXED CODE ###

### C

def gcd(a, b):
    if a == 0:
        return b
    if b == 0:
        return a
    if b > a:
        a, b = b, a 
    return gcd(b, a%b)

N = int(input())
A = [int(x) for x in input().split()]

left = [0] * (N+1)
right = [0] *(N+1)

for i in range(N):
    left[i+1] = gcd(A[i], left[i])
for i in reversed(range(N)):
    right[i] = gcd(A[i], right[i+1])
    
res = 0
for i in range(N):
    l = left[i]
    r = right[i+1]
    res = max(gcd(l, r), res)

print(res)
S = list(int, map(input().split()))
ans1 = 0
ans2 = 0
for i in range (len(S)):
  if i % 2 == 0:
    if S[i] == 0:
      ans1 += 1
  else:
    if S[i] == 1:
      ans1 += 1
for i in range(len(S)):
  if i % 2 == 0:
    if S[i] == 1:
      ans2 += 1
  else:
    if S[i] == 0:
      ans2 += 1
print(min(ans1, ans2))



### FIXED CODE ###

S = list(map(int, input()))
ans1 = 0
ans2 = 0
for i in range (len(S)):
  if i % 2 == 0 and S[i] == 0:
      ans1 += 1
  elif i %2 ==1 and S[i] == 1:
      ans1 += 1
for i in range(len(S)):
  if i % 2 == 0 and S[i] == 1:
      ans2 += 1
  elif i % 2 ==1 and S[i] == 0:
      ans2 += 1
print(min(ans1, ans2))
n=int(input())
a=[]*n
kei=0
for i in range(0,n,1):
    a[i]=int(input())
    kei=kei+a[i]

a.sort(reverse=True)
kei=kei-a[0]/2
print("%d",kei)

### FIXED CODE ###

n=int(input())
a=[0]*n
kei=0
for i in range(0,n,1):
    a[i]=int(input())
    kei=kei+a[i]

a.sort(reverse=True)
kei=kei-a[0]//2
print(kei)
s1 = input()
print("Yes" if input() in tuple(s1[i:] + s1[:i] for i in range(len(s1))) else "No")


### FIXED CODE ###

import numpy as np
A = np.array(sorted(map(int, input().split())))
print((A[1:] - A[:-1]).sum())
a,b,c=map(int,input().spli())
print(min(c,b//a))

### FIXED CODE ###

a,b,c=map(int,input().split())
print(min(c,b//a))
# coding: utf-8

N, Q = map(int, input().split())
S = input()

## S中で、'AC'であるインデックスを求める
index = [0] * N
i = 0
while i < len(S)-1:
    if S[i]=='A' and S[i+1]=='C':
        index[i] = 1
        i += 2
    else:
        i += 1
num = [sum(index[i]) for i in range(N)]

#print('\n')
#print(index)

for i in range(Q):
    l, r = map(int, input().split())
    l = l-1
    r = r-1
    print( num[r] - num[l] )


### FIXED CODE ###

# coding: utf-8

N, Q = map(int, input().split())
S = input()

num = [0] * (N+1)

for i in range(N):
    #if S[i]=='A' and S[i+1]=='C':
    if S[i:i+2] =='AC':
        num[i + 1] = num[i] + 1
    else:
        num[i + 1] = num[i]

        

for i in range(Q):
    l, r = map(int, input().split())
    print( num[r-1] - num[l-1] )
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])
    
def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]

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

graph=np.zeros((n,n))

for i in range(m):
    graph[a[i]-1][b[i]-1] = 1
    graph[b[i]-1][a[i]-1] = 1

d,p=shortest_path(graph,return_predecessors=True)
flag = 0
ans = []
for i in range(1, n):
    michi = get_path(0, i, p)
    if len(michi) == 0:
        print('No')
        flag = 1
        break
    else:
        ans.append(michi[-2]+1)
        print(ans)
if flag == 0:
    print('Yes')
    for i in ans:
        print(i)

### FIXED CODE ###

n,m=map(int,input().split())
g=[[] for _ in range(n)]

for _ in range(m):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

from collections import deque

def bfs(u):
    queue = deque([u])
    d=[-1]*n
    pre=[-1]*n
    d[u]=0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is -1:
                if pre[i] == -1:
                    pre[i]=v
                d[i]=d[v]+1
                queue.append(i)
    return d,pre
d,pre=bfs(0)
print('Yes')

for i in range(n):
    if i==0:
        continue
    print(pre[i]+1)
"""
rootを決めて、aから必ずrootを通ってbに到達するとする
aとbのlcaより上は、+2されることになるので、実質通っていないのと同値
どんな木であっても、自分自身が偶数回(0を含む)でてこないと
ノードの値は偶数にはなりえない
"""
n, m = map(int, input().split())
cnts = [0] * (n+1) 
for i in range(n):
    a,b = map(int, input().split())
    cnts[a] += 1
    cnts[b] += 1
if all([c%2 == 0 for c in cnts]):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

"""
rootを決めて、aから必ずrootを通ってbに到達するとする
aとbのlcaより上は、+2されることになるので、実質通っていないのと同値
どんな木であっても、自分自身が偶数回(0を含む)でてこないと
ノードの値は偶数にはなりえない
"""
n, m = map(int, input().split())
cnts = [0] * (n+1) 
for i in range(m):
    a,b = map(int, input().split())
    cnts[a] += 1
    cnts[b] += 1
if all([c%2 == 0 for c in cnts]):
    print("YES")
else:
    print("NO")
b, c = map(int, input().split())
print(B*C-B-C+1)

### FIXED CODE ###

B, C = map(int, input().split())
print(B*C-B-C+1)
N = int(input())
sum = 0
for i in range(1,N+1)
	sum += i
print(sum)

### FIXED CODE ###

N = int(input())
sum = 0
for i in range(1,N+1):
	sum += i
print(sum)
import re
s, t = input().replace('?', '.'), input()
l, m = len(s), len(t)

if l < m:
    print("UNRESTORABLE")
    exit()

can = []  # candidates
for i in range(l - m + 1):
    if re.match(s[i:i + m], t)
        can.append((s[:i] + t + s[i + m:]).replace('.', 'a'))
print(min(can) if can else "UNRESTORABLE")

### FIXED CODE ###

import re
s, t = input().replace('?', '.'), input()
l, m = len(s), len(t)

if l < m:
    print("UNRESTORABLE")
    exit()

can = []  # candidates
for i in range(l - m + 1):
    if re.match(s[i:i + m], t):
        can.append((s[:i] + t + s[i + m:]).replace('.', 'a'))
print(min(can) if can else "UNRESTORABLE")
import numpy as np
N = int(input())
print(np.mean([*map(lambda x: x % 2, np.arange(1, N+1))]))

### FIXED CODE ###

import numpy as np
N = int(input())
a = np.arange(1, N+1)
print((a % 2).mean())
A,B,K = [int(i) for i in input().split()]
if (A>B):
    A,B=B,A
f=[]
j=A
for i in range(1,A):
    if (i>=j):
        break
    if (A % i == 0 and B % i == 0):
        j=int(A/i)
        f.append(i)
        if (B % j == 0):
            f.append(j)
if A==1:
    print(1)
else:
    print(f[K-1])




### FIXED CODE ###

A,B,K = [int(i) for i in input().split()]
if (A>B):
    A,B=B,A
k=0
for i in reversed(range(1,A+1)):
    if (A % i == 0 and B % i == 0):
        k+=1
    if (k==K):
        print(i)
        break
x, y = map(int, input().split())
if (x+Y)%2 == 0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

x, y = map(int, input().split())
if (x*y)%2 == 0:
  print("Even")
else:
  print("Odd")
import sys
sys.setrecursionlimit(10**6)

N = int(input())
content = [0]*(10**9+2)
for i in range(N):
    ai = int(input())
    if content[ai]==1:
        content[ai]=0
    else:
        content[ai]=1
print(sum(content))


### FIXED CODE ###

from collections import Counter
N = int(input())
A = []
for i in range(N):
    ai = int(input())
    A.append(ai)
dic = Counter(A)
cnt=0
for idx, val in dic.items():
    if val%2 != 0:
        cnt+=1
print(cnt)
targ = int(input())
while True:
    minans = float("inf")
    if (targ ** ( 1 / 3)) == int(targ ** ( 1 / 3)):
        z = int(targ ** ( 1 / 3))
        targ = 0
    elif (targ ** ( 1 / 2)) == int(targ ** ( 1 / 2)):
        y = int(targ ** ( 1 / 2))
        targ = 0
    else:
        for n in range(math.ceil(targ ** ( 1 / 3))):
            if minans == 0:
                break
            m = int(math.sqrt(targ - n**3))
            if (n ** 3) + (m **2) > targ:
                break
            if minans > targ - (n ** 3 + m**2) + n + m:
                minans = targ - (n ** 3 + m**2) + n + m
    if minans != float("inf"):
        print(minans)
    else:
        print(y + z)
    targ = int(input())
    if targ == 0:
        break
            

### FIXED CODE ###

import math
targ = int(input())
y,z = 0,0
while True:
    minans = float("inf")
    for n in range(math.ceil(targ ** ( 1 / 3))+1):
        if minans == 0:
            break
        if targ - n**3 >= 0:
            m = int((targ - n**3) **(1/2))
        else:
            m = 0
        if (n ** 3) + (m **2) > targ:
            break
        if minans > targ - (n ** 3 + m**2) + n + m:
            minans = targ - (n ** 3 + m**2) + n + m
    if minans != float("inf"):
        print(minans)
    else:
        print(y + z)
    targ = int(input())
    if targ == 0:
        break
a,b=input().split()
a=int(a)
b=int(b)
c=list(map(int,input().split()))
m=a*b
for i in range(a):
  if c[i+1]-c[i]<b:
    m=m-(b-(c[i+1]-c[i]))
print(m)

### FIXED CODE ###

a,b=input().split()
a=int(a)
b=int(b)
c=list(map(int,input().split()))
m=a*b
for i in range(a-1):
  if c[i+1]-c[i]<b:
    m=m-(b-(c[i+1]-c[i]))
print(m)
s = input()
k = int(input())
for int(c) in s:
  if c != 1:
    print(c)
    exit(0)

### FIXED CODE ###

s = input()
k = int(input())

for c in s:
  if c == '1':
    k -= 1
    if k == 0:
      print(1)
      break
  else:
    print(c)
    break
import numpy as np
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=np.full(n+k,10**10,dtype=np.int64)
dp[0]=0
for i in range(1,n):
  dp[i:i+k+1]=np.minimum(dp[i:i+k+1],dp[i]+np.abs(h[i:i+k+1]-h[i]))
print(dp[n-1])
        

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
m=max(h)*(n-1)
dp=[m]*n
dp[0]=0
for i in range(n):
  if i+1+k<=n:
    r=k
  else:
    r=n-i-1
  for kk in range(1,r+1):
    dp[i+kk]=min(dp[i+kk],dp[i]+abs(h[i+kk]-h[i]))
print(dp[n-1])
def fib(n):
    f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
    return int(f)

# def fib(n):
#     a, b = 0, 1
#     if n == 1:
#         return a
#     elif n == 2:
#         return b
#     else:
#         for i in range(n-2):
#             a, b = b, a + b
#         return b

n,m = map(int,input().split())
a =  [int(input()) for i in range(m)]
a.append(n+1)

time_f=[]

for i,v in enumerate(a):
    if i == 0:
        # print (fib(a[i]))
        time_f = fib(a[i])
    else:
        # print((a[i]-a[i-1]-1))
        # print (fib(a[i]-a[i-1]-1))
        time_f *=fib(a[i]-a[i-1]-1)


print(time_f%1000000007)

### FIXED CODE ###

n,m = map(int,input().split())
a =  [int(input()) for i in range(m)]

dp =[0]*(n+1)

for i in a:
    dp[i] = -1

for i in [0,1]:
    if dp[i] == -1:
        dp[i] =0
    else:
        dp[i] =1

for i in range(2,n+1):
    if dp[i] == -1:
        dp[i] = 0
    else:
        if dp[i-1]==dp[i-2]==0:break
        dp[i] = (dp[i-2]+dp[i-1])

print(dp[-1]%1000000007)
s=str(input())
t=str(input())
temps=list(set(s))
tempt=list(set(t))
temps=sorted(list(temps))
tempt=sorted(list(tempt))
for i in range(0,len(temps)):
  temps[i]=s.count(temps[i])
for i in range(0,len(tempt)):
  tempt[i]=t.count(tempt[i])
count=0
for i in range(0,len(temps)):
  if temps[i]==tempt[i]:
    count=count+1
if count==len(temps):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s=str(input())
t=str(input())
temp=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
s=list(s)
t=list(t)
temps=[0]*len(temp)
tempt=[0]*len(temp)
for i in range(0,len(temp)):
  temps[i]=s.count(temp[i])
  tempt[i]=t.count(temp[i])
temps.sort()
tempt.sort()
if temps==tempt:
  print("Yes")
else:
  print("No")
n,m=map(int,input().split())

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

X.sort()

C=[]
for i in range(m-1):
    c=abs(X[i+1]-X[i])
    C.append(c)

C.sort()

sum_c=0
for  j in range(n+1):
    sum_c+=C[j]
    
print(sum_c)

### FIXED CODE ###

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

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

X.sort()

C=[]
for i in range(m-1):
    c=abs(X[i+1]-X[i])
    C.append(c)

if(n>=m):
    print(0)
else:
    C.sort()
    sum_c=0
    for j in range(len(C)-n+1):
        sum_c+=C[j]
    print(sum_c)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
N, K = list(map(int, input().split()))

MAX = N
PRIME = 10 ** 9 + 7

fac = [0] * MAX
finv = [0] * MAX


def invMod(a, m):
    a %= m
    b, x, y = m, 1, 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        x -= t * y
        x, y = y, x
    return x % m


def binomInit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, MAX):
        fac[i] = (fac[i - 1] * i) % PRIME
        finv[i] = (finv[i - 1] * invMod(i, PRIME)) % PRIME
        

def binom(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % PRIME


binomInit()
    
    
max_i = min(K, N - K + 1)

for i in range(1, max_i + 1):
    blue_part = 1 if K - i == 0 else binom(K - 1, i - 1)
    red_part = 1 if (N - K) - (i - 1) == 0 else binom(N - K + 1, i)
    print((blue_part * red_part) % PRIME)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
N, K = list(map(int, input().split()))
max_i = min(K, N - K + 1)

MAX = N * 2
PRIME = 10 ** 9 + 7

fac = [0] * MAX
finv = [0] * MAX


def invMod(a, m):
    a %= m
    b, x, y = m, 1, 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        x -= t * y
        x, y = y, x
    return x % m


def binomInit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, MAX):
        fac[i] = (fac[i - 1] * i) % PRIME
        finv[i] = (finv[i - 1] * invMod(i, PRIME)) % PRIME
        

def binom(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % PRIME


binomInit()
    

for i in range(1, K + 1):
    blue_part = binom(K - 1, i - 1)
    red_part = binom(N - K + 1, i)
    print((blue_part * red_part) % PRIME)
from fractions import gcd 

n = int(input())
a_set = set(map(int, input().split()))
max_a = max(a_set)
min_sub = max_a


if len(a_set) == 1:
    print(a_list[0])
    exit()
elif 1 in a_set:
    print(1)
    exit()
else:
    for val in a_set:
        min_sub = min(gcd(max_a, val), min_sub)
        if min_sub == 1:
            print(1)
            exit()
print(min_sub)

### FIXED CODE ###

from fractions import gcd 

n = int(input())
a_set = set(map(int, input().split()))
max_a = max(a_set)
min_sub = max_a

for val in a_set:
    min_sub = min(gcd(max_a, val), min_sub)
    if min_sub == 1:
        print(1)
        exit()
print(min_sub)
import math
n = []
while True:
    try:
        n.append(int(raw_input()))
    except:
        break
 
r = max(n)+1
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for range(2*i+1,r,i+1)]
           
for i in n:
     print sum(p[:i])

### FIXED CODE ###

import math
n = []
while True:
    try:
        n.append(int(raw_input()))
    except:
        break
  
r = max(n)+1
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
p[3::2] = [0 for x in range(3,r,2)]
for i in range(2,sqrt,2):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)] 
  
for i in n:
     print sum(p[:i])
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

c = 0

while (True):
    if A[0] < B[0] and A[0] <= K:
        K -= A.pop(0)
        c += 1

    elif B[0] <= K:
        K -= B.pop(0)
        c += 1

    else:
        break

print(c)

### FIXED CODE ###

def is_ok(arg):
    return not Alist[arg] <= t
    

def bisect(ok, ng):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

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

Alist = [0]
for i in range(N):
    Alist.append(Alist[i] + A[i])

ans = 0
for i in range(N+1):
    if Alist[i] <= K:
        ans = i
    else:
        break

b = 0
for i in range(M):
    b += B[i]
    t = K - b

    if t >= 0:
        res = bisect(N + 1, -1)
        ans = max(ans, i + res)

    else:
        break

print(ans)