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

def main():
    import heapq
    from sys import stdin
    input=stdin.readline
    xs,ys,xt,yt=map(int,input().split())
    n=int(input())
    xyr=[[xs,ys,0],[xt,yt,0]]+[list(map(int,input().split())) for _ in [0]*n]
    g=[[] for _ in [0]*(n+2)]
    for i in range(n+1):
        x1,y1,r1=xyr[i]
        for j in range(i+1,n+2):
            x2,y2,r2=xyr[j]
            d_temp=max(0,((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2)
            g[i].append((j,d_temp))
            g[j].append((i,d_temp))
    d=[0]*(n+2)
    visit=[False]*(n+2)
    visit[0]=True
    h=[]
    for i,j in g[0]:
        h.append((j,i))
    heapq.heapify(h)
    while h:
        i,j=heapq.heappop(h)
        if visit[j]==True:
            continue
        visit[j]=True
        d[j]=i
        for k,l in g[j]:
            if visit[k]==False:
                heapq.heappush(h,(l+i,k))
    print(d[1])
main()


### FIXED CODE ###

def main():
    import heapq
    from sys import stdin
    input=stdin.readline
    xs,ys,xt,yt=map(int,input().split())
    n=int(input())
    xyr=[[xs,ys,0],[xt,yt,0]]+[list(map(int,input().split())) for _ in [0]*n]
    g=[[] for _ in [0]*(n+2)]
    for i in range(n+1):
        x1,y1,r1=xyr[i]
        for j in range(i+1,n+2):
            x2,y2,r2=xyr[j]
            d_temp=max(0,((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2)
            g[i].append((j,d_temp))
            g[j].append((i,d_temp))
    d=[0]*(n+2)
    visit=[False]*(n+2)
    visit[0]=True
    h=[]
    for i,j in g[0]:
        h.append((j,i))
    heapq.heapify(h)
    while h:
        i,j=heapq.heappop(h)
        if visit[j]==True:
            continue
        visit[j]=True
        d[j]=i
        for k,l in g[j]:
            if visit[k]==False:
                heapq.heappush(h,(l+i,k))
    print(d[1])
main()
### BUGGY CODE ###

a = int(input())
sum = 1
nums = list(map(int, input().strip().split()))
for i in range(a):
  sum *= nums[i]
if sum<=10**18 :  
	print(sum)
else:
  print(-1)


### FIXED CODE ###

def main ():
	N = int(input())
	A = list(map(int,input(). split ()))

	if 0 in  A:
		print(0)
		return

	prod = 1
	for a in A:
		prod *= a
		if prod > 1000000000000000000:
			print(-1)
			return

	print(prod)

main ()
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, q = list(map(int, readline().split()))
    event = [0] * (2 * n + q)

    for i in range(n):
        s, t, x = map(int, readline().split())
        event[i * 2] = (s - x, x, 0)
        event[i * 2 + 1] = (t - x, x, 1)

    for i in range(q):
        d = int(input())
        event[2 * n + i] = (d, 0, 2)

    from operator import itemgetter
    event.sort(key=itemgetter(0))
    stop = set()
    
    for t, x, ev_type in event:
        if ev_type == 0:
            stop.add(x)
        elif ev_type == 1:
            stop.discard(x)
        else:
            if stop:
                print(min(stop))
            else:
                print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, q = list(map(int, readline().split()))
    event = [0] * (2 * n + q)

    for i in range(n):
        s, t, x = list(map(int, readline().split()))
        event[i * 2] = (s - x, x, 0)
        event[i * 2 + 1] = (t - x, x, 1)

    for i in range(q):
        d = int(input())
        event[2 * n + i] = (d, 0, 2)

    from operator import itemgetter
    event.sort(key=itemgetter(0))
    stop = set()
    res = INF

    for t, x, ev_type in event:
        if ev_type == 0:
            stop.add(x)
            if res == -1:
                res = x
            elif res > x:
                res = x
        elif ev_type == 1:
            stop.discard(x)
            if res == x:
                if stop:
                    res = min(stop)
                else:
                    res = -1
        else:
            if stop:
                print(res)
            else:
                print(-1)


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

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

res = 0
for i in range(len(A)):
    temp = 0
    for j in range(i, len(A)):
        temp += A[j]
        if temp == 0:
            res += 1
print(res)

### FIXED CODE ###

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

C = [0 for _ in A]
C[0] = A[0]
for i in range(1, len(A)):
    C[i] = C[i-1] + A[i]

from collections import Counter

count = Counter(C)

li = list(count.values())

res = 0
for l in li:
    if l == 1:
        pass
    else:
        res += l * (l - 1) / 2
res += count[0]

print(int(res))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

r, g, b, n = map(int, input().split())

count = 0

a = list()

a.append(r)
a.append(b)
a.append(g)

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

for i in range(0, n//a[0]+1):
    b = n - i*a[0]
    for j in range(0, b//a[1]+1):
        c = b - j*a[1]
        for k in range(0, c//a[2]+1):
            if c == k*a[2]:
                count += 1

# for i in range(0, n+1):
#     for j in range(0, n+1):
#         for k in range(0, n+1):
#             if r*i + g*j + b*k == n:
#                 count += 1


print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-

r, g, b, n = map(int, input().split())

count = 0

for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        if (n - i*r - j*g) % b == 0:
            count += 1

# やってはいけないやつ
# for i in range(0, n+1):
#     for j in range(0, n+1):
#         for k in range(0, n+1):
#             if r*i + g*j + b*k == n:
#                 count += 1

print(count)
### BUGGY CODE ###

import itertools

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))
    NEXT=[NOWSUM[i]%mod  if i<=a else 0 for i in range(K+1)]
    #print(NEXT)

    for j in range(a+1,K+1):
        NEXT[j]=(NOWSUM[j]-NOWSUM[j-a-1])%mod


    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K]%mod)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for i in range(N):
    NEXT=[0]*(K+1)
    NOWSUM=[0]
    for n in NOW:
        NOWSUM.append(NOWSUM[-1]+n)
        
    for j in range(K+1):
        NEXT[j]=(NEXT[j]+NOWSUM[j+1]-NOWSUM[max(0,j-A[i])])%mod

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])
### BUGGY CODE ###

import numpy as np 
H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])

yoko = [[0 for _ in range(W)] for _ in range(H)]
tate =  [[0 for _ in range(W)] for _ in range(H)]

for h in range(H):
    cnt = 0
    for w in range(W):
        if grid[h][w] == ".":
            cnt += 1
        else:
            cnt = 0
        yoko[h][w] = cnt

for w in range(W):
    cnt = 0
    for h in range(H):
        if grid[h][w] == ".":
            cnt += 1
        else:
            cnt = 0
        tate[h][w] = cnt

tate = np.array(tate)
yoko = np.array(yoko)

for h in range(H):
    my_max = 0
    for w in range(W):
        if yoko[h][W - 1 - w] != 0:
            my_max = max(my_max, yoko[h][W - 1 - w])
            yoko[h][W - 1 - w] = my_max
        else:
            my_max = 0

tate = tate.T

for h in range(W):
    my_max = 0
    for w in range(H):
        if tate[h][H - 1 - w] != 0:
            my_max = max(my_max, tate[h][H - 1 - w])
            tate[h][H - 1 - w] = my_max
        else:
            my_max = 0
            
tate = tate.T

ans = -10000
for h in range(H):
    for w in range(W):
        ans = max(ans, tate[h][w] + yoko[h][w] - 1)
print(ans)



### FIXED CODE ###

H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])
    
left = [[0 for _ in range(W)] for _ in range(H)]
right = [[0 for _ in range(W)] for _ in range(H)]
up = [[0 for _ in range(W)] for _ in range(H)]
down = [[0 for _ in range(W)] for _ in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == ".":
            if w == 0:
                left[h][w] = 1
            else:
                left[h][w] += left[h][w - 1] + 1

for h in range(H):
    for w in range(W)[::-1]:
        if grid[h][w] == ".":
            if w == W - 1:
                right[h][w] = 1
            else:
                right[h][w] += right[h][w + 1] + 1
            
for w in range(W):
    for h in range(H):
        if grid[h][w] == ".":
            if h == 0:
                up[h][w] = 1
            else:
                up[h][w] += up[h - 1][w] + 1
                
for w in range(W):
    for h in range(H)[::-1]:
        if grid[h][w] == ".":
            if h == H - 1:
                down[h][w] = 1
            else:
                down[h][w] += down[h + 1][w] + 1
                
ans = -10000
for h in range(H):
    for w in range(W):
        ans = max(ans, up[h][w] + down[h][w] + right[h][w] + left[h][w] - 3)
print(ans)
### BUGGY CODE ###

import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush
def resolve():
    m, n, k = map(int, input().split())
    si, sj, ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]
    dist = [[[(INF, 0)] * 4 for _ in range(n)] for _ in range(m)]
    heap = []
    for i in range(4):
        dist[si][sj][i] = (0, 0)
        heappush(heap, (0, 0, si, sj, i))

    D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while heap:
        d, r, i, j, dir = heappop(heap)
        if dist[i][j][dir] != (d, r):
            continue
        # change direction
        for ndir in range(4):
            nd = (d + (r > 0), 0)
            if dist[i][j][ndir] > nd:
                dist[i][j][ndir] = nd
                heappush(heap, (nd[0], nd[1], i, j, ndir))
        # move to forth
        di, dj = D[dir]
        ni, nj = i + di, j + dj
        if not (0 <= ni < m and 0 <= nj < n):
            continue
        if grid[ni][nj] == '@':
            continue
        nd = (d + 1, 0) if r == k - 1 else (d, r + 1)
        if dist[ni][nj][dir] > nd:
            dist[ni][nj][dir] = nd
            heappush(heap, (nd[0], nd[1], ni, nj, dir))

    ans = INF
    for dir in range(4):
        d, r = dist[ti][tj][dir]
        ans = min(ans, d + (r > 0))
    if ans == INF:
        ans = -1
    print(ans)
resolve()

### FIXED CODE ###

import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    m, n, k = map(int, input().split())
    si, sj, ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]

    dist = [[INF] * n for _ in range(m)]
    dist[si][sj] = 0
    D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque([(si, sj)])
    while queue:
        i, j = queue.popleft()
        for di, dj in D:
            for s in range(1, k + 1):
                ni, nj = i + s * di, j + s * dj
                if not (0 <= ni < m and 0 <= nj < n):
                    break
                if grid[ni][nj] == '@':
                    break
                if dist[ni][nj] <= dist[i][j]:
                    break
                if dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    queue.append((ni, nj))

    ans = dist[ti][tj]
    if ans == INF:
        ans = -1
    print(ans)
resolve()
### BUGGY CODE ###

n,k,q = list(map(int,input().split()))
a = [int(input()) for i in range(q)]
t = ["No"]*n
for i in range(1,max(a)+1):
    if k - q > 0:
        print(*["Yes"]*n,sep="\n")
        exit()
    elif k + a.count(i) - q > 0 :
        t[i-1] = "Yes"
print(*t,sep="\n")

### FIXED CODE ###

n,k,q = list(map(int,input().split()))
t = [0]*n
for i in range(q):
    t[int(input())-1] += 1

print(*["Yes" if k + i - q > 0 else "No" for i in t],sep="\n")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
i = 0
sum_before = 0
sum_after = 0
count = 0
while i < n:
    sum_after = sum_before + a[i]
    if sum_after * sum_before > 0 or sum_after == 0:
        count += 1
        if sum_after < 0:
            a[i] += 1
        elif sum_after > 0:
            a[i] -= 1
        elif sum_before < 0:
            a[i] += 1
        else:
            a[i] -= 1
    else:
        i += 1
        sum_before = sum_after

print(count)
 




### FIXED CODE ###

import numpy as np
import copy
n = int(input())
a = list(map(int, input().split()))
a_copy = copy.copy(a)
count = np.zeros(2)


i = 0
sum_before = 0
sum_after = 0    
    
if a[0] <= 0:
    count[0] += abs(a[0]) + 1
    a[0] = 1
while i < n:
    sum_after = sum_before + a[i]
    if sum_after * sum_before > 0 or sum_after == 0:
        if sum_after < 0:
            a[i] = a[i] - sum_after + 1
        elif sum_after > 0:
            a[i] = a[i] - sum_after - 1
        elif sum_before < 0:
            a[i] += 1
        else:
            a[i] -= 1
        count[0] += abs(sum_after) + 1
        sum_after = sum_before + a[i]
    i += 1
    sum_before = sum_after

i = 0
sum_before = 0
sum_after = 0    

if a_copy[0] >= 0:
    count[1] += abs(a_copy[0]) + 1
    a_copy[0] = -1

while i < n:
    sum_after = sum_before + a_copy[i]
    if sum_after * sum_before > 0 or sum_after == 0:
        if sum_after < 0:
            a_copy[i] = a_copy[i] - sum_after + 1
        elif sum_after > 0:
            a_copy[i] = a_copy[i] - sum_after - 1
        elif sum_before < 0:
            a_copy[i] += 1
        else:
            a_copy[i] -= 1
        count[1] += abs(sum_after) + 1
        sum_after = sum_before + a_copy[i]
    i += 1
    sum_before = sum_after

print(int(min(count[0], count[1])))
### BUGGY CODE ###

n,m = map(int,input().split())
isl1,isl2 = [0]*m,[0]*m
for i in range(m):
    (isl1[i], isl2[i]) = map(int,input().split())
    isl1[i] -= 1
    isl2[i] -= 1
boss = [-1]*n
mem = [1]*n
dpt = [0]*n
ans = [0]*m
s = (n*(n-1))//2
ans[m-1] = s
 
def sea(island, boss):
     m = 0
     while boss[island] >= 0:
          island = boss[island]
          m += 1
     return island,m
 
for j in range(m-1):
     i = m-j-1
     i1,i2 = isl1[i],isl2[i]
     p1,m1 = sea(i1, boss)
     p2,m2 = sea(i2, boss)
     if p1 != p2:
          if dpt[m1] < dpt[m2]:
               (p1,p2) = (p2,p1)
          boss[p2] = p1
          s -= mem[p1]*mem[p2]
          mem[p1] += mem[p2]
          mem[p2] = 0
          dpt[p1] = max(dpt[p1],dpt[p2]+1)
     ans[i-1] = s
         
for i in range(m):
     print(ans[i])

### FIXED CODE ###

#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])
### BUGGY CODE ###

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

for i in range(n):
    l = a.pop(i)
    print(max(a))
    a.insert(i, l)


### FIXED CODE ###

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

max_1st = max(a)
max_2nd = sorted(a)[-2]
for i in range(n):
    if a[i] == max_1st:
        print(max_2nd)
    else:
        print(max_1st)
### BUGGY CODE ###

n = int(input())
cnt = 0
for a in range(1,n):
    i = 1
    while a * i < n:
        if a * (i+1000000) < n:
            cnt += 1000000
            i += 1000000
        else:
            cnt += 1
            i += 1
    
print(cnt)

### FIXED CODE ###

n = int(input())
cnt = 0
for a in range(1,n):
    cnt += (n-1) // a
    
print(cnt)
### BUGGY CODE ###

n=int(input())
S=input()
R=[]
G=[]
B=[]
for i in range(n):
	if S[i]=='R':
		R.append(i+1)
	elif S[i]=='G':
		G.append(i+1)
	else:
		B.append(i+1)
r=len(R)
g=len(G)
b=len(B)

c=0
for i in R:
	for j in B:
		d=abs(i-j)
		min_n=min(i,j)
		max_n=max(i,j)
		if max_n+d in G:
			c+=1
		if (i+j)%2==0 and (i+j)//2 in G:
			c+=1
		if min_n-d in G:
			c+=1

print(r*g*b-c)

### FIXED CODE ###

n=int(input())
S=input()
R=[]
G=[]
B=[]
for i in range(n):
	if S[i]=='R':
		R.append(i)
	elif S[i]=='G':
		G.append(i)
	else:
		B.append(i)
r=len(R)
g=len(G)
b=len(B)

c=0
for i in range(n):
	for j in range(i+1,n):
		k=2*j-i
		if k<n:
			if len(set([S[i],S[j],S[k]]))==3:
				c+=1

print(r*g*b-c)
### BUGGY CODE ###

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

bridges = []
for i in range(m):
    bridges.append([int(x) for x in input().split()])
'''
g = list(range(n+1))
ng = [1 for _ in range(n+1)]
gl = [[i] for i in range(n+1)]
ans = []
unconf = n*(n-1)//2
ans.append(unconf)


for x in reversed(bridges):
    a,b = x
    if g[a] != g[b]:
        tmp = ng[g[a]] * ng[g[b]]
        ng[g[a]] = ng[g[a]]+ng[g[b]]
        gl[g[a]] = gl[g[a]] + gl[g[b]]
        for y in gl[g[b]]:
            g[y] = g[a]
        unconf -= tmp
        ans.append(unconf)
    else:
        ans.append(unconf)


ans.reverse()
ans.pop(0)
for x in ans:
    print(x)
'''
def root(par, ifpar, a):
    while ifpar[a] != 1:
       a = par[a]
    return a 

def unite(cnt, par, ifpar, npar, ra, rb):
    if cnt % 2 == 0:
        npar[ra] = npar[ra] + npar[rb]
        par[rb] = ra
        ifpar[rb] = 0
    else:
        npar[rb] = npar[rb] + npar[ra]
        par[ra] = rb
        ifpar[ra] = 0

par = list(range(n+1))
ifpar = [1 for _ in range(n+1)]
npar = [1 for _ in range(n+1)]

ans = []
unconf = n*(n-1)//2
ans.append(unconf)
cnt = 0

for x in reversed(bridges):
    a,b = x
    ra = root(par, ifpar, a)
    rb = root(par, ifpar, b)
    if ra != rb:
        tmp = npar[ra] * npar[rb]
        unite(cnt, par, ifpar, npar, ra, rb)
        unconf -= tmp
    ans.append(unconf)
    cnt += 1

ans.reverse()
ans.pop(0)
for x in ans:
    print(x)



















### FIXED CODE ###

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

bridges = []
for i in range(m):
    bridges.append([int(x) for x in input().split()])
'''
g = list(range(n+1))
ng = [1 for _ in range(n+1)]
gl = [[i] for i in range(n+1)]
ans = []
unconf = n*(n-1)//2
ans.append(unconf)


for x in reversed(bridges):
    a,b = x
    if g[a] != g[b]:
        tmp = ng[g[a]] * ng[g[b]]
        ng[g[a]] = ng[g[a]]+ng[g[b]]
        gl[g[a]] = gl[g[a]] + gl[g[b]]
        for y in gl[g[b]]:
            g[y] = g[a]
        unconf -= tmp
        ans.append(unconf)
    else:
        ans.append(unconf)


ans.reverse()
ans.pop(0)
for x in ans:
    print(x)
'''
def root(par, ifpar, a):
    while ifpar[a] != 1:
       a = par[a]
    return a 

def unite(cnt, par, ifpar, npar, depth, ra, rb):
    if depth[ra] >= depth[rb]:
        npar[ra] = npar[ra] + npar[rb]
        par[rb] = ra
        ifpar[rb] = 0
        if depth[ra] == depth[rb]:
            depth[ra] += 1
    else:
        npar[rb] = npar[rb] + npar[ra]
        par[ra] = rb
        ifpar[ra] = 0

par = list(range(n+1))
ifpar = [1 for _ in range(n+1)]
npar = [1 for _ in range(n+1)]
depth = [1 for _ in range(n+1)]

ans = []
unconf = n*(n-1)//2
ans.append(unconf)
cnt = 0

for x in reversed(bridges):
    a,b = x
    ra = root(par, ifpar, a)
    rb = root(par, ifpar, b)
    if ra != rb:
        tmp = npar[ra] * npar[rb]
        unite(cnt, par, ifpar, npar, depth, ra, rb)
        unconf -= tmp
    ans.append(unconf)
    cnt += 1

ans.reverse()
ans.pop(0)
for x in ans:
    print(x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


n = int(input())
li = [[int(x) for x in row.split()][::-1] for row in sys.stdin.readlines()]

cnt = 0
check = []
play = 0

while play < n*(n-1) // 2:
    s = play
    for i in range(1,n):
        if i in check or len(li[i-1]) == 0:
            continue
        temp = li[i-1][-1]
        if temp <= i:
            continue
        if li[temp-1][-1] == i and temp not in check:
            del li[i-1][-1]
            del li[temp-1][-1]
            play += 1
            check.append(temp)
    cnt += 1
    check = []
    
    if s == play:
        print(-1)
        exit()

print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
A = [[-1] + [int(x)-1 for x in row.split()][::-1] for row in sys.stdin.readlines()]
 
A.append([-1])

def f(cand):
    cand1 = set()
    can_use = []
    for n in cand:
        if A[A[n][-1]][-1] == n:
            can_use.append(n)
    for n in can_use:
        A[n].pop()
        cand1.add(n)
        if A[n][-1] != -1:
            cand1.add(A[n][-1])
    return len(can_use), cand1
    
answer = 0
rest = N*(N-1)
cand = set(range(N))
while True:
    answer += 1
    x,cand = f(cand)
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break
    
print(answer)
### BUGGY CODE ###

import fractions
# import math as fractions
n = int(input())
a = list(map(int, input().split()))
ans = a[0]
mod = 10**9+7
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
# print(ans)
sum = 0
for i in range(n):
    sum += ans//a[i]
    sum %= mod
print(sum)


### FIXED CODE ###

import fractions
# import math as fractions
mod = 10**9+7
n = int(input())
a = list(map(int, input().split()))

if n == 1:
    print(1)
    exit()

g = fractions.gcd(a[0], a[1])
f = a[0]*a[1]//g
ans = a[0]//g+a[1]//g

for i in range(2, n):
    # print(ans, g, f)
    h = fractions.gcd(f, a[i])
    g = a[i] // h
    f = f*a[i]// h
    ans *= g
    ans += f // a[i]
    ans %= mod
print(ans%mod)
### BUGGY CODE ###

import numpy as np
H, W, D = map(int, input().split())
grid = np.array([[0, 0]] * (H * W))
for i in range(H):
    Ai = list(map(int, input().split()))
    for j in range(W):
        grid[Ai[j] - 1] = [i, j]
Q = int(input())
tasks = [list(map(int, input().split())) for _ in range(Q)]

accum = [[]] * D
for i in range(D):
    diff = (abs(np.diff(grid[i::D, 0])) + abs(np.diff(grid[i::D, 1])))
    accum[i] = [0] + list(np.cumsum(diff))

for q in range(Q):
    Li, Ri = tasks[q]
    res = (Li - 1) % D
    x = (Li - 1) // D
    y = (Ri - 1)// D
    print(accum[res][y] - accum[res][x])


### FIXED CODE ###

import numpy as np
H, W, D = map(int, input().split())
grid = np.array([[0, 0]] * (H * W))
for i in range(H):
    Ai = list(map(int, input().split()))
    for j in range(W):
        grid[Ai[j] - 1] = [i, j]
Q = int(input())
tasks = [list(map(int, input().split())) for _ in range(Q)]

accum = [0] * (H*W)
for i in range(H * W):
    if i >= D:
        accum[i] = accum[i - D] + abs(grid[i][0] - grid[i - D][0]) + abs(grid[i][1] - grid[i - D][1])

for q in range(Q):
    Li, Ri = tasks[q]
    print(accum[Ri - 1] - accum[Li - 1])
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
x = sorted(LIST())
ans = math.inf
v = [0]*n

if n >= m:
    print(0)
    exit()

for v[1:n] in itertools.combinations(range(1,m),n-1):
    tmp = 0
    for i in range(n):
        if(i<n-1):
            tmp += x[v[i+1]-1]-x[v[i]]
        else:
            tmp += x[m-1]-x[v[i]]
    ans = min(ans, tmp)
print(ans)

### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
x = sorted(LIST())
dx = [x[i+1]-x[i] for i in range(m-1)]
dx.sort(reverse=True)

if n >= m:
    print(0)
else:
    print(x[m-1]-x[0]-sum(dx[0:n-1]))