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

import sys

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

List=[]
max_list=[]

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


for i in range(len(X_list)):
	if i==len(X_list)-1:
		break
	tmp=abs(X_list[i]-X_list[i+1])
	List.append(tmp)
	if N==1:
		pass

	elif len(max_list)<N-1:
		max_list.append(tmp) 
	elif len(max_list)==N-1:
		if min(max_list)<tmp:
			max_list.append(tmp)
			max_list.remove(min(max_list))
		else:
			pass
	else:
		pass

cnt=sum(List)-sum(max_list)

print(cnt)


### FIXED CODE ###

import sys
import numpy as np

N, M = map( int, input().split() )
X_list = np.array( sorted( list( map( int, input().split() ) ) ) )

diff=np.diff(X_list, n=1)

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

sorted_diff=np.sort(diff)

cnt=np.sum(sorted_diff[:M-N])

print(cnt)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

X,Y,Z,K = LI()
A = LI()
B = LI()
C = LI()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

h = A[0] + B[0] + C[0]
l = 0
while h > l+1:
    m = (h+l) // 2

    num = 0
    for a in A:
        last_num = num
        j = len(C) - 1
        for i in B:
            while i + C[j] < m - a:
                j -= 1
                if j < 0: break
            else:
                num += j + 1
                continue
            break
        if last_num == num: break
    if num > K:
        l = m
    else:
        h = m

ans = []
cnt = 0
for a in A:
    j = len(C) - 1
    last_cnt = cnt
    for i in B:

        while i + C[j] < l - a:
            j -= 1
            if j < 0: break
        else:
            for k in range(j+1):
                ans.append(a+i+C[k])
                cnt += 1
            continue
        break
    if last_cnt == cnt: break
ans.sort(reverse=True)
print (*ans[:K],sep='\n')



### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

X,Y,Z,K = LI()
A = LI()
B = LI()
C = LI()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

h = A[0] + B[0] + C[0]
l = 0
while h > l+1:
    m = (h+l) // 2

    num = 0
    for a in A:
        j = len(C) - 1
        for i in B:
            while i + C[j] < m - a:
                j -= 1
                if j < 0: break
            else:
                num += j + 1
                continue
            break
    if num > K:
        l = m
    else:
        h = m

ans = []
cnt = 0
for a in A:
    j = len(C) - 1
    last_cnt = cnt
    for i in B:

        while i + C[j] <= l - a:
            j -= 1
            if j < 0: break
        else:
            for k in range(j+1):
                ans.append(a+i+C[k])
                cnt += 1
            continue
        break
ans.sort(reverse=True)
for _ in range(K-len(ans)):
    ans.append(l)
print (*ans[:K],sep='\n')
### BUGGY CODE ###


if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    
    N, K = map(int,input().split())
    WD = [list(map(int,input().split())) for _ in range(N)]
    #W = [elem[0] for elem in WD]
    #D = [elem[1] for elem in WD]

    def solve(tgt):
        res = 0
        for w,d in WD:
            res += max(0, (tgt-w)//d+1)
        if res >= K:
            return True
        else:
            return False

    ok = 4*(10 ** 18)  # exist
    ng = 0  # not exist
    while abs(ok - ng) > 1:
        cnt = (ok + ng) // 2
        if solve(cnt):
            ok = cnt
        else:
            ng = cnt
    print(ok)
    

### FIXED CODE ###

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    
    N, K = map(int,input().split())
    WD = [tuple(map(int,input().split())) for _ in range(N)]

    def solve(tgt):
        res = 0
        for w,d in WD:
            res += max(0, (tgt-w)//d+1)
        if res >= K:
            return True
        else:
            return False

    ok = 2*(10 ** 18)  # exist
    ng = 0  # not exist
    while abs(ok - ng) > 1:
        cnt = (ok + ng) // 2
        if solve(cnt):
            ok = cnt
        else:
            ng = cnt
    print(ok)
### BUGGY CODE ###

a=int(input())
b=0
c=int(a**(1/2))
for i in range(c+1):
    for j in range(-c,c):
        if((i**5)-(j**5)==a):
            b=1
            break
    if(b==1):
        break
print(i,j)

### FIXED CODE ###

a=int(input())
b=0
c=int(a**(1/2))
for i in range(-1000,1000):
    for j in range(-1000,1000):
        if((i**5)-(j**5)==a):
            b=1
            break
    if(b==1):
        break
print(i,j)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7

#繰り返し2乗法
def  mod_pow(a:int, b:int, mod:int)->int:
    if b % 2 == 0:
        return (mod_pow(a, b//2, mod) ** 2) % mod
    elif b == 1:
        return a % mod
    else:
        return ((mod_pow(a, b//2, mod) ** 2) * a) % mod

#逆元を求める関数
def mod_inverse(mod:int, b:int)->int:
    return mod_pow(b, mod-2, mod)

#aCbをmodで割った余りを求める関数(bが小さい)
def nCr_mod(n:int, r:int, mod:int)->int:
    num, den = 1, 1 #numerator, denominator

    for i in range(r):
        num *= (n-i) % mod
        den *= (i+1) % mod

    return (num * mod_inverse(mod, den)) % mod
    
ans = (mod_pow(2, n, mod) - 1 - nCr_mod(n, a, mod) - nCr_mod(n, b, mod)) % mod
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7

#繰り返し2乗法
def  mod_pow(a:int, b:int, mod:int)->int:
    if b % 2 == 0:
        return (mod_pow(a, b//2, mod) ** 2) % mod
    elif b == 1:
        return a % mod
    else:
        return ((mod_pow(a, b//2, mod) ** 2) * a) % mod

#逆元を求める関数
def mod_inverse(mod:int, b:int)->int:
    return mod_pow(b, mod-2, mod)

#aCbをmodで割った余りを求める関数(bが小さい)
def nCr_mod(n:int, r:int, mod:int)->int:
    num, den = 1, 1 #numerator, denominator

    for i in range(r):
        num = (num * (n-i)) % mod
        den = (den * (i+1)) % mod

    return (num * mod_inverse(mod, den)) % mod

""""
print(mod_pow(2,n, mod))
print(nCr_mod(n, a, mod))
print(nCr_mod(n, b, mod))
"""

ans = (mod_pow(2, n, mod) - 1 - nCr_mod(n, a, mod) - nCr_mod(n, b, mod)) % mod
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int,input().split())

ans = 0
for i in range(N//R+1):
    for j in range(N//G+1):
        if  N -R*i -G*j == 0:
            ans += 1
        elif N -R*i -G*j > 0 and (N -R*i -G*j) % B == 0:
            ans += 1

print(ans)

### FIXED CODE ###

R, G, B, N = map(int,input().split())

ans = 0
for i in range(N//R+1):
    for j in range((N- R*i)//G+1):
        if (N -R*i -G*j) % B == 0:
            ans += 1

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

H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = []
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l.append([x, y])
  
c = max(h)
d = max(w)
a = [i for i, x in enumerate(h) if x == c]
b = [i for i, x in enumerate(w) if x == d]

flag = False
for s in a:
  for t in b:
    if [s, t] not in l:
      flag = True
      break
if flag:
  ans = c+d
else:
  ans = c+d-1
print(ans)


### FIXED CODE ###

H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = set()
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l.add((x, y))
  
c = max(h)
d = max(w)
a = [i for i, x in enumerate(h) if x == c]
b = [i for i, x in enumerate(w) if x == d]

flag = False
for s in a:
  for t in b:
    if (s, t) not in l:
      flag = True
      break
  if flag:
    break
ans = c+d
if not flag:
  ans -= 1
print(ans)
### BUGGY CODE ###

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort()
ln = max(max(a), max(b)).bit_length() + 1
table = [[0] * N for _ in range(ln)]
for i in range(ln):
  for j in range(N): table[i][j] = b[j] % (1 << (i + 1))
  table[i].sort()
#print(table)
res = 0
ttable = [0] * ln
for t in a:
  for i in range(ln):
    x = t % (1 << (i + 1))
    #print(t, x)
    if x <= 1 << i:
      l = bl(table[i], (1 << i) - x)
      r = bl(table[i], (1 << (i + 1)) - x)
      ttable[i] ^= max(0, r - l) % 2
    else:
      r = bl(table[i], (1 << (i + 1)) - x)
      l = bl(table[i], (1 << (i + 1)) + (1 << i) - x)
      ttable[i] ^= (r + max(0, N - l)) % 2
for i in range(ln): res += ttable[i] * (1 << i)
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = 0
ln = max(max(a), max(b)).bit_length() + 1
for i in range(ln):
  y = (1 << (i + 1))
  u = [x % y for x in a]
  v = [x % y for x in b]
  y >>= 1
  u.sort(reverse = True)
  v.sort()
  t = 0
  k = 0
  kk = 0
  for x in u:
    while k < N and x + v[k] < y: k += 1
    t += N - k
    while kk < N and x + v[kk] < y * 2: kk += 1
    t -= N - kk
  k = 0
  kk = 0
  #print(t)
  for x in u:
    while k < N and x + v[k] < y * 2 + y: k += 1
    t += N - k
    while kk < N and x + v[kk] < y * 4: kk += 1
    t -= N - kk
    #print(t)
  #print(u, v, t)
  res ^= t % 2 * y
print(res)
### BUGGY CODE ###

n,m,q=map(int,input().split())
alist=[]
for i in range(m):
    l,r=map(int,input().split())
    alist.append([l,r])
alist.sort()
alist.reverse()
for j in range(q):
    count=0
    p,q=map(int,input().split())
    for j in alist:
        if p<=j[0] and q>=j[1]:
            count+=1
        elif p>j[0]:
            break
    print(count)

### FIXED CODE ###

n, m, Q = map(int, input().split())
lr = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    lr[l][r] += 1

rui = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        rui[i][j] = lr[i][j] + rui[i - 1][j] + rui[i][j - 1] - rui[i - 1][j - 1]
    
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    ans = rui[q][q] - rui[p][q] - rui[q][p] + rui[p][p]
    print(ans)
### BUGGY CODE ###

import io,sys
sys.setrecursionlimit(10**6)

def main():
    import bisect
    n = int(input())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A.sort()

    ans = 0
    a_max = A[-1]
    note = [True]*(a_max+1)
    for j in range(n):
        a = A[j]
        if note[a]:
            if j != n-1 and A[j]==A[j+1]:
                ans-=1
            ans+=1
            for i in range(a,a_max+1):
                if i%a==0:
                    note[i] = False

        
    
    print(ans)
main()

### FIXED CODE ###

import io,sys
sys.setrecursionlimit(10**6)

def main():
    import bisect
    n = int(input())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A.sort()

    ans = 0
    a_max = A[-1]
    note = [True]*(a_max+1)
    for j in range(n):
        a = A[j]
        if note[a]:
            if j != n-1 and A[j]==A[j+1]:
                ans-=1
            ans+=1
            # for i in range(a,a_max+1):
            #     if i%a==0:
            #         note[i] = False
            temp = a 
            while temp <= a_max:
                note[temp]=False
                temp+=a

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

n=int(input())
L=list(map(int,input().split()))
L.sort()
 
count=0
list.sort(L, reverse=True)
 
for i in range(n):
    for j in range(i+1,n):
        count += len([k for k in L[j+1:] if k > L[i]-L[j]])

print(count)

### FIXED CODE ###

import bisect

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

L.sort()

s=0
for i in range(n-1):
      for j in range(i+1,n):
            index=bisect.bisect_left(L,L[i]+L[j])
            s+=index-(j+1)
print(s)
### BUGGY CODE ###

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

S = set(range(N))
A_list = []
B_list = []

for _ in range(M):
  A, B = map(int, input().split())
  A_list.append(A - 1)
  B_list.append(B - 1)

for A, B in zip(A_list, B_list):
  A_height = H[A]
  B_height = H[B]
  
  if A_height <= B_height:
    S = S - set([A])
  
  if B_height <= A_height: 
    S = S - set([B])
  
  
print(len(S)) 
 

### FIXED CODE ###

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


A_list = []
B_list = []
Remove_list = []

for _ in range(M):
  A, B = map(int, input().split())
  A_list.append(A - 1)
  B_list.append(B - 1)

for A, B in zip(A_list, B_list):
  A_height = H[A]
  B_height = H[B]
  
  if A_height <= B_height:
    Remove_list.append(A)
  
  if B_height <= A_height: 
    Remove_list.append(B)
  
S = set(range(N))
S = S - set(Remove_list)

print(len(S))
### BUGGY CODE ###

N = int(input())
"""
yとzで残り
"""
from math import sqrt
for n in range(1,N+1):
    cnt = 0
    for x in range(1,n+1):
        for y in range(1,n+1):
            for z in range(1,n+1):
                if x**2+y**2+z**2+x*y+y*z+z*x == n:
                    cnt += 1
    print(cnt)

### FIXED CODE ###

N = int(input())
"""
yとzで残り
"""
memo = {}
from math import sqrt
for x in range(1,int(sqrt(N))+1):
    for y in range(1,int(sqrt(N))+1):
        for z in range(1,int(sqrt(N))+1):
            n = x**2+y**2+z**2+x*y+y*z+z*x
            if n not in memo:
                memo[n] = 0
            memo[n] += 1

for i in range(1,N+1):
    if i in memo:
        print(memo[i])
    else:
        print(0)
### BUGGY CODE ###

S = list(input())
cnt = 0
while len(set(S)) !=1:
    if S[-1] == 'W':
        j=1
        while S[-j] != 'B':
            S[-j] = 'B'
            j+=1
        S.append('B')
    elif S[-1] == 'B':
        j=1
        while S[-j] != 'W':
            S[-j] = 'W'
            j+=1
        S.append('W')
    cnt += 1
print(cnt)

### FIXED CODE ###

S = list(input())
cnt = 0
key = S[0]
for i in range(1,len(S)):
    if key != S[i]:
        key = S[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

a, b, c, k = map(int, input().split())

suma = 0

for i in range(k):
    if a == 0 and b == 0:
        suma = suma - k
        break
    elif a == 0 and c == 0:
        break
    elif b == 0 and c == 0:
        suma = suma + k
        break
    if a > 0:
        a = a - 1
        k = k - 1
        suma += 1
    elif b > 0:
        b = b - 1
        k = k - 1
    elif c > 0:
        c = c - 1
        k = k - 1
        suma -= 1
print(suma)

### FIXED CODE ###

a, b, c, k = map(int, input().split())

suma = 0


if k > a:
    if k > a + b:
        if k == a + b + c:
            print(a - c)
        else:
            k = k - (a + b)
            print(a-k)
    else:
        print(a)
else:
    print(k)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
  print(A.count(i))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
l = [0]*N
for i in range(1,N):
  l[A[i-1]-1] += 1
for i in range(N):
  print(l[i])
### BUGGY CODE ###

S=list(input())
N=len(S)
mod=[0 for i in range(2019)]
s=0
for i in range(N-1,-1,-1): 
  s+=int(S[i])*(10**(N-1-i))
  mod2=s%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)      

### FIXED CODE ###

import numpy as np
S=input()
N=len(S)
mod=[0 for i in range(2019)]
mod2=0
ten=1
for i in range(N-1,-1,-1): 
  s=int(S[i])*ten
  mod2+=np.mod(s,2019)
  mod2=np.mod(mod2,2019)
  mod[mod2]+=1
  ten=(ten*10)%2019
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())

count = 0
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if x + y + z == S:
                count += 1

print(count)

### FIXED CODE ###

K, S = map(int, input().split())

count = 0
for x in range(K + 1):
    for y in range(K + 1):
        if 0 <= S - x - y <= K:
            count += 1

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

L=input()
l=len(L)
ans=3**(l-1)
a=L.count('1')
cnt=1
for i in range(1,l):
    if L[i]=='1':
        ans+=(2**(cnt))*(3**(l-i-1))
        cnt+=1
        
print((ans+2**a)%(10**9+7))

### FIXED CODE ###

mod=10**9+7

L=input()
l=len(L)
ans=3**(l-1)
a=L.count('1')
cnt=1

for i in range(1,l):
    if L[i]=='1':
        ans+=pow(2,cnt,mod)*pow(3,l-i-1,mod)
        cnt+=1
        
print((ans+pow(2,a,mod))%mod)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
s = 0
if n % 2 == 0:
    b = [int(i) for i in range(n) if i % 2 == 1]
    for i in b:
        c = a.count(i)
        if c != 2:
            s = 1
            break
    ans = 2 ** len(b) % (10**9 + 7)
else:
    b = [int(i) for i in range(n) if i % 2 == 0]
    for i in b:
        c = a.count(i)
        
        
        if c == 1 and i == 0:
            ans = 1
        elif c != 2:
            s = 1
            break
    ans = 2 ** (len(b)-1) % (10**9 + 7)

if s == 0:
    print(ans)
elif s == 1:
    print('0')

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
s = 0
b = 0
d = [0]*n
if n % 2 == 0:
    for i in a:
        d[i] += 1 
    for i in range(1,n,2):
        if d[i] != 2:
            s = 1
            break
        else:
            b += 1
    ans = 2 ** b % (10**9 + 7)
else:
    for i in a:
        d[i] += 1 
    
    for i in range(0,n,2):
        if i == 0 and d[0] == 1:
            ans = 1
        elif d[i] != 2:
            s = 1
            break
        else:
            b += 1
    ans = 2 ** (b) % (10**9 + 7)

if s == 0:
    print(ans)
elif s == 1:
    print('0')
### BUGGY CODE ###

N, K  = map(int, input().split())
h = list(map(int, input().split()))

inf = 10 ** 4 + 1
dp = [inf] * N
dp[0] = 0
dp[1] = abs(h[1]- h[0])

for i in range(2, N):
    dp[i] =  min( [dp[j] + abs(h[i] - h[j]) for j in range(max(0, i-K), i)])

print(dp[N-1])


### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
### BUGGY CODE ###

n, m = map(int, input().split())
index = 0
listForL = []
listForL2 = []
while index < m:
    p, y = map(int, input().split())
    listForL.append([p, y])
    listForL2.append([p, y])
    index+=1

listForL2.sort()
listForId=[]
index2 =0
count = 0
before=0
while index2 < len(listForL2):
    if before!=listForL2[index2][0]:
        count=1
        before = listForL2[index2][0]
    else:
        count+=1
    mojiR=str(listForL2[index2][0])
    mojiL=str(count)
    index3=0
    if len(mojiR)==1:
        mojiR="00000"+mojiR
    elif len(mojiR)==2:
        mojiR = "0000"+mojiR
    elif len(mojiR)==3:
        mojiR = "000"+mojiR
    elif len(mojiR)==4:
        mojiR = "00"+mojiR
    elif len(mojiR)==5:
        mojiR = "0"+mojiR
    if len(mojiL) == 1:
        mojiL = "00000"+mojiL
    elif len(mojiL) == 2:
        mojiL = "0000"+mojiL
    elif len(mojiL) == 3:
        mojiL = "000"+mojiL
    elif len(mojiL) == 4:
        mojiL = "00"+mojiL
    elif len(mojiR) == 5:
        mojiL = "0"+mojiL
    index2+=1
    listForId.append(mojiR+mojiL)

index5=0
while index5 < len(listForL):
    targetI = listForL2.index(listForL[index5])
    print(listForId[targetI])
    index5+=1

### FIXED CODE ###

n, m = map(int, input().split())
index = 0
listForL = []
listForL2 = []
while index < m:
    p, y = map(int, input().split())
    listForL.append([p, y])
    listForL2.append([p, y, index])
    index+=1

listForL2.sort()
listForAns=[0]*m
index2 =0
count = 0
before=0
while index2 < len(listForL2):
    if before!=listForL2[index2][0]:
        count=1
        before = listForL2[index2][0]
    else:
        count+=1
    mojiR=str(listForL2[index2][0])
    mojiL=str(count)
    index3=0
    if len(mojiR)==1:
        mojiR="00000"+mojiR
    elif len(mojiR)==2:
        mojiR = "0000"+mojiR
    elif len(mojiR)==3:
        mojiR = "000"+mojiR
    elif len(mojiR)==4:
        mojiR = "00"+mojiR
    elif len(mojiR)==5:
        mojiR = "0"+mojiR
    if len(mojiL) == 1:
        mojiL = "00000"+mojiL
    elif len(mojiL) == 2:
        mojiL = "0000"+mojiL
    elif len(mojiL) == 3:
        mojiL = "000"+mojiL
    elif len(mojiL) == 4:
        mojiL = "00"+mojiL
    elif len(mojiL) == 5:
        mojiL = "0"+mojiL
    listForAns[listForL2[index2][2]]=mojiR+mojiL
    index2+=1

for ans in listForAns:
    print(ans)
### BUGGY CODE ###

import sys
import heapq
my_input = sys.stdin.readline

def main():
    xs, ys, xt, yt = map(int, my_input().split())
    N = int(my_input())
    C = [(xs, ys, 0), (xt, yt, 0)]
    C += [tuple(map(int, my_input().split())) for i in range(N)]

    G = [[] for i in range(N+2)]
    for i in range(N + 2):
        for j in range(i + 1, N + 2):
            cost = max(0, ((C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2) ** 0.5 - (C[i][2] + C[j][2]))
            G[i].append((j, cost))
            G[j].append((i, cost))


    def dijkstra(graph, start, inf=float('inf')):
        import heapq
        n = len(graph)
        distances = [inf] * n
        distances[start] = 0
        visited = [False] * n

        # 距離・頂点
        hq = [(0, start)]
        while hq:
            dist, fr = heapq.heappop(hq)
            if fr == 1:
                return distances
            visited[fr] = True

            for to, cost in graph[fr]:
                new_dist = distances[fr] + cost
                if (visited[to]) or (distances[to] <= new_dist):
                    continue

                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

        return distances


    dist = dijkstra(G, 0)
    print(dist[1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import heapq
my_input = sys.stdin.readline

def main():
    xs, ys, xt, yt = map(int, my_input().split())
    N = int(my_input())
    C = [(xs, ys, 0), (xt, yt, 0)]
    C += [tuple(map(int, my_input().split())) for i in range(N)]

    G = [[] for i in range(N+2)]
    for i in range(N + 2):
        for j in range(i + 1, N + 2):
            cost = max(0, ((C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2) ** 0.5 - (C[i][2] + C[j][2]))
            G[i].append((j, cost))
            G[j].append((i, cost))


    def dijkstra(graph, start, inf=float('inf')):
        import heapq
        n = len(graph)
        distances = [inf] * n
        distances[start] = 0
        visited = [False] * n

        # 距離・頂点
        hq = [(0, start)]
        while hq:
            dist, fr = heapq.heappop(hq)
            if distances[fr] < dist:
                continue
            if fr == 1:
                return distances
            visited[fr] = True

            for to, cost in graph[fr]:
                new_dist = distances[fr] + cost
                if (visited[to]) or (distances[to] <= new_dist):
                    continue

                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

        return distances


    dist = dijkstra(G, 0)
    print(dist[1])


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

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
for i in range(M):
    a = A.index(max(A))
    A[a] = int(A[a]/2)

print(sum(A))

### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
    A[i] = (-1)*A[i]

heapq.heapify(A)

for i in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, int(a/2))

print(abs(sum(A)))