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

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
DP = [0]
for i in range(N-1):
    act = float("inf")
    for k in range(K):
        if i-k < 0 : continue
        act = min(DP[-1-k] + abs(h[i-k]-h[i+1]) , act)
    DP += [act]
 
print(DP[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]
for i in range(n-1):
    cnt = float("inf")
    for j in range(k):
        if i-j < 0: continue
        cnt = min(dp[-1-j] + abs(h[i-j]-h[i+1]), cnt)
        #print("i =",i,"j =",j,"i-j =",i-j,"i+j =",i+j,"cnt =",cnt)
    dp.append(cnt)
print(dp[-1])
### BUGGY CODE ###


n = int(input())

ans = 0
for i in range(n):
    ans += i
print(ans)


### FIXED CODE ###


n = int(input())

print((1 + (n - 1)) * (n - 1) // 2)
### BUGGY CODE ###

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


### FIXED CODE ###

import collections
workers = int(input())
A = list(map(int, input().split()))
new = collections.Counter(A)
for i in range(1,workers+1):
    print(new[i])
### BUGGY CODE ###

N, M = map(int, input().split())
card = False
for _ in range(M):
    L, R = map(int, input().split())
    if card is not False:
        card = card & set([i for i in range(L, R + 1)])
    else:
        card = set([i for i in range(L, R + 1)])
print(len(card))

### FIXED CODE ###

N, M = map(int, input().split()) 
left = 1
right = N
for _ in range(M):
    L, R = map(int, input().split())
    if left < L:
        left = L
    if R < right:
        right = R
    if left > right:
        print(0)
        exit()
print(right - left + 1)
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
def main():
    H,W = map(int,input().split())
    S = [list(input().rstrip()) for _ in range(H)]
    L = np.zeros((H,W))
    R = np.zeros((H,W))
    U = np.zeros((H,W))
    D = np.zeros((H,W))
    for i in range(H):
        for j in range(W):
            if j == 0:
                if S[i][j] == "#":
                    L[i,j] = -1
                continue
            if S[i][j] == ".":
                L[i,j] += L[i,j-1]+1
            else:
                L[i,j] = -1
        for j in reversed(range(W)):
            if j == W-1:
                if S[i][j] == "#":
                    R[i,j] = -1
                continue
            if S[i][j] == ".":
                R[i,j] += R[i,j+1]+1
            else:
                R[i,j] = -1
    for j in range(W):
        for i in range(H):
            if i == 0:
                if S[i][j] == "#":
                    U[i,j] = -1
                continue
            if S[i][j] == ".":
                U[i,j] += U[i-1,j]+1
            else:
                U[i,j] = -1
        for i in reversed(range(H)):
            if i == H-1:
                if S[i][j] == "#":
                    D[i,j] = -1
                continue
            if S[i][j] == ".":
                D[i,j] += D[i+1,j]+1
            else:
                D[i,j] = -1
    su = L+R+U+D
    #print(L,R,U,D,sep="\n")
    print(int(np.amax(su)+1))
if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
def main():
    H,W = map(int,input().split())
    S = np.array([list(input().rstrip()) for _ in range(H)]) == "."
    L = np.zeros((H,W),dtype=int)
    R = np.zeros((H,W),dtype=int)
    U = np.zeros((H,W),dtype=int)
    D = np.zeros((H,W),dtype=int)
    #[-1]はインデックス内(all 0)なのでエラーを吐かない！
    for i in range(H):
        U[i] = (U[i-1]+1)*S[i]
        D[-i-1] = (D[-i]+1)*S[-i-1]  
    for j in range(W):
        L[:,j] = (L[:,j-1]+1)*S[:,j]
        R[:,-j-1] = (R[:,-j]+1)*S[:,-j-1]

    su = L+R+U+D
    #print(L,R,U,D,sep="\n")
    print(np.amax(su)-3)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

s = input()
t = input()
dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]
for i in range(1, len(s)+1):
    for j in range(1, len(t)+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + s[i-1]
        else:
            if len(dp[i-1][j]) > len(dp[i][j-1]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
print(dp[len(s)][len(t)])

### FIXED CODE ###

s = ' ' + input()
t = ' ' + input()
dp = [[0 for _ in range(len(t))] for _ in range(len(s))]
for i in range(1, len(s)):
    for j in range(1, len(t)):
        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

i, j = len(s)-1, len(t)-1
ret = ''
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ret += s[i]; i -= 1; j -= 1
print(ret[::-1])
### BUGGY CODE ###

import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def count(xmin, xmax, ymin, ymax):
    num = 0
    for i in range(N):
        x,y = points[i]
        if (xmin <= x and xmax >= x) and (ymin <= y and ymax >= y):
            num += 1
    return num

ans = INF
for i in range(N):
    for j in range(i,N):
        for k in range(N):
            for l in range(k,N):
                if count(to_search_x[i], to_search_x[j], to_search_y[k], to_search_y[l]) >= K:
                    ans = min(ans, (to_search_x[j]-to_search_x[i])*(to_search_y[l]-to_search_y[k]))

print(ans)


### FIXED CODE ###

import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
points_matrix = [[0]*(N+1) for i in range(N+1)]
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def count(xmin, xmax, ymin, ymax):
    num = 0
    for i in range(N):
        x,y = points[i]
        if (xmin <= x and xmax >= x) and (ymin <= y and ymax >= y):
            num += 1
    return num

for n in range(N):
    for i in range(N):
        for j in range(N):
            if points[n][0] <= to_search_x[i] and points[n][1] <= to_search_y[j]:
                points_matrix[i+1][j+1] += 1

ans = INF
for i in range(N):
    for j in range(i,N):
        for k in range(N):
            for l in range(k,N):
                if (points_matrix[i][k] + points_matrix[j+1][l+1] - points_matrix[i][l+1] - points_matrix[j+1][k]) >= K:
                    ans = min(ans, (to_search_x[j]-to_search_x[i])*(to_search_y[l]-to_search_y[k]))

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

import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**3
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    P = LI()

    seat = [[1] * N for _ in range(N)]
    zero = [[1] * N for _ in range(N)]

    ans = 0

    for i in P:
        x = (i-1) % N
        y = (i-1) // N
        min_cnt = INF
        if x == 0 or x == N-1 or y == 0 or y == N-1:
            min_cnt = 0
        else:

            dp = [[INF] * N for _ in range(N)]
            d = 0
            f = 0
            q = collections.deque()
            q.append((f,d,x,y))
            dp[x][y] = 0
            while q:
                f,d,i,j = q.popleft()
                if d > min(x,N-x,y,N-y): break
                for di,dj in ((1,0),(0,1),(-1,0),(0,-1)):
                    if not(0 <= i+di < N and 0 <= j+dj < N):
                        min_cnt = min(min_cnt,f)
                        continue
                    if zero[i+di][j+dj] == 0:
                        min_cnt = min(min_cnt,f)
                        continue
                    e = seat[i+di][j+dj]
                    if dp[i+di][j+dj] > f+e:
                        dp[i+di][j+dj] = f+e
                        q.append((f+e,d,i+di,j+dj))

        seat[x][y] = 0
        if min_cnt == 0:
            zero[x][y] = 0
        ans += min_cnt
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    P = LI()

    s = []
    for i in range(N):
        for j in range(N):
            s.append(min(i,N-1-i,j,N-1-j))

    r = [1] * (N*N)

    ans = 0
    q = []
    for p in P:
        p -= 1
        ans += s[p]
        r[p] = 0
        q.append(p)
        while q:
            a = q.pop()
            nc = s[a] + r[a]

            if a >= N:
                if s[a-N] > nc:
                    s[a-N] = nc
                    q.append(a-N)
            if a + N < N*N:
                if s[a+N] > nc:
                    s[a+N] = nc
                    q.append(a+N)
            if a % N:
                if s[a-1] > nc:
                    s[a-1] = nc
                    q.append(a-1)
            if a % N < N -1:
                if s[a+1] > nc:
                    s[a+1] = nc
                    q.append(a+1)

    print(ans)

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

def resolve():
    import math
    def primes(n):
        ass = []
        is_prime = [True] * (n + 1)
        is_prime[0] = False
        is_prime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if not is_prime[i]:
                continue
            for j in range(i * 2, n + 1, i):
                is_prime[j] = False
        for i in range(len(is_prime)):
            if is_prime[i]:
                ass.append(i)
        return ass

    def divisor(n):
        ass = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                if i != 1:
                    ass.append(i)
                if i ** 2 == n:
                    continue
                ass.append(n // i)
        return ass


    n = int(input())
    a = list(map(int, input().split()))
    pair = False
    divisors = set(divisor(a[0]))
    ggcd = a[0]
    for i in range(1, n):
        divs = set(divisor(a[i]))
        if len(divs & divisors) != 0:
            pair = True
        else:
            divisors = set(list(divisors) + list(divs))
        ggcd = math.gcd(ggcd, a[i])
    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")
resolve()

### FIXED CODE ###

def resolve():
    import math
    n = int(input())
    a = list(set(map(int, input().split())))
    maxa = max(a)

    ggcd = a[0]
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break

    pair = False

    c = [0] * (10**6+ 1)
    for i in a:
        c[i] += 1

    for i in range(2, maxa+1):
        cnt = 0
        for j in range(i, maxa+1, i):

            cnt += c[j]
        if cnt > 1:
            pair = True

    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")
resolve()
### BUGGY CODE ###

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

### FIXED CODE ###

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

N, K = map(int, input().split())
h = list(map(int, input().split()))
#dp[i] をiまでの最小コスト
INF = 10**9
# h.extend([INF for i in range(100)])
dp = [INF for i in range(N)]
dp[0] = 0
for i in range(N):
    for k in range(1,K+1):
        if i + k >= N:
            break
        dp[i + k] = min(dp[i + k], dp[i] + abs(h[i+k] - h[i])) # i => i+k でのコストの更新
print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
#dp[i] をiまでの最小コスト
INF = 10**9
# h.extend([INF for i in range(100)])
dp = [INF for i in range(N)]
dp[0] = 0
for i in range(N):
    for k in range(1,K+1):
        if i + k >= N:
            break
        dp[i + k] = min(dp[i + k], dp[i] + abs(h[i+k] - h[i])) # i => i+k でのコストの更新
print(dp[N-1])
### BUGGY CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline

K = int(input())
ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd(gcd(i, j), k)

print(ans)


### FIXED CODE ###

import sys
from math import gcd
input = sys.stdin.readline

K = int(input())
ans = 0

for i in range(1, K+1):
    for j in range(i, K+1):
        for k in range(j, K+1):
            if i == j and k == i:
                ans += gcd(gcd(i, j), k)
            elif i == j or k == i or j == k:
                ans += 3 * gcd(gcd(i, j), k)
            else:
                ans += 6 * gcd(gcd(i, j), k)

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

N,A,B = map(int,input().split())
count = 0
flag = True
while flag:
    if N >= A:
        N = N - A
        count += A
    else:
        count += N
        N = 0
        flag = False
    if N >= B:
        N = N - B
    else:
        N = 0
        flag = False
print(count)

### FIXED CODE ###

N,A,B = map(int,input().split())
C = A + B
 
shou = N // C
amari = N % C
if amari >= A:
    print(A * shou + A)
else:
    print(A * shou + amari)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(n):
    if a[i]<n:
        for j in range(a[i],n):
            if j-i==a[i]+a[j]:
                cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
d={}
ans=0
for i in range(n):
    if i+a[i] in d.keys():
        d[i+a[i]]+=1
    else:
        d[i+a[i]]=1
    if i-a[i] in d.keys():
        ans+=d[i-a[i]]
print(ans)
### BUGGY CODE ###

n = int(input())
S = input()

# keyは(色、jの位置)のタプル
dp = {}

ans = 0

for i in range(n - 2):
    c_i = S[i]
    for j in range(i + 1, n - 1):
        if S[j] == c_i:
            continue
        c_j = S[j]
        d_ij = j - i
        if (c_i, c_j, j) in dp:
            ans += dp[(c_i, c_j, j)]
            if j + d_ij < n:
                c_k = S[j + d_ij]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    ans -= 1
        else:
            tmp = 0
            for k in range(j + 1, n):
                c_k = S[k]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    tmp += 1
            dp[(c_i, c_j, j)] = tmp
            if j + d_ij < n:
                c_k = S[j + d_ij]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    tmp -= 1
            ans += tmp
print(ans)


### FIXED CODE ###

n = int(input())
S = input()

# keyは(色、jの位置)のタプル
dp = {}

ans = 0

for i in range(n - 2):
    c_i = S[i]
    for j in range(i + 1, n - 1):
        if S[j] == c_i:
            continue
        c_j = S[j]
        d_ij = j - i
        if (c_i, j) in dp:
            ans += dp[(c_i, j)]
            if j + d_ij < n:
                c_k = S[j + d_ij]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    ans -= 1
        else:
            tmp = 0
            for k in range(j + 1, n):
                c_k = S[k]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    tmp += 1
            dp[(c_i, j)] = tmp
            if j + d_ij < n:
                c_k = S[j + d_ij]
                if c_i != c_j and c_j != c_k and c_k != c_i:
                    tmp -= 1
            ans += tmp
print(ans)
### BUGGY CODE ###

import sys
def b(bs, cs):
    #print(bs, xs[len(bs):])
    d = set()
    bl, cl = len(bs), len(cs)
    bi, ci = 0, 0
    while True:
      if bs[bi] > cs[ci]:
        bi += 1
        bs.append(cs[ci])
        del cs[ci]
      else:
        ci += 1
      if bi == bl or ci == len(cs):
        break
    if len(bs) != 2 * bl:
      print("No")
      sys.exit()
    return bs, cs

n=int(input())
xs = sorted(list(map(int,input().split())))[::-1]
bs, cs = xs[:1], xs[1:]
for _ in range(n):
    bs, cs = b(sorted(bs)[::-1], sorted(cs)[::-1])

print("Yes")



### FIXED CODE ###

import sys
def b(bs, cs):
    d = set()
    bl, cl = len(bs), len(cs)
    bi, ci = 0, 0
    ncs = []
    while True:
      if bs[bi] > cs[ci]:
        bs.append(cs[ci])
        bi += 1
      else:
        ncs.append(cs[ci])
      ci += 1
      if bi == bl or ci == cl:
        break
    if len(bs) != 2 * bl:
      print("No")
      sys.exit()
    return bs, ncs + cs[ci:]

n=int(input())
xs = sorted(list(map(int,input().split())))[::-1]
bs, cs = xs[:1], xs[1:]
for _ in range(n):
    bs, cs = b(sorted(bs)[::-1], cs)

print("Yes")
### BUGGY CODE ###

n = int(raw_input())
ax = []
bx = []
for _ in xrange(n):
    a,b = map(int,raw_input().split())
    ax.append(a)
    bx.append(b)

ax.reverse()
bx.reverse()
cnt = 0
for i in xrange(n):
    if ax[i] % bx[i] !=0:
        k = bx[i] - (ax[i] % bx[i])
        cnt += k
        ax = map(lambda x:x+k,ax)
print cnt


### FIXED CODE ###

n = int(raw_input())
ax = []
bx = []
for _ in xrange(n):
    a,b = map(int,raw_input().split())
    ax.append(a)
    bx.append(b)

ax = ax[::-1]
bx = bx[::-1]
cnt = 0
for i in xrange(n):
    if (ax[i] + cnt) % bx[i] !=0:
        k = bx[i] - ((ax[i] + cnt) % bx[i])
        cnt += k

print cnt
### BUGGY CODE ###

from bisect import bisect
N=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
B_reverse=B[::-1]
C=sorted(list(map(int,input().split())))
cnt=0
dict={}
val=0
for b in B_reverse:
    c_min=bisect(C,b)
    val+=len(C[c_min:])
    dict[b]=val
for a in A:
    b_min=bisect(B,a)
    if b_min==len(B):
        pass
    else:
        cnt+=dict[B[b_min]]
print(cnt)

### FIXED CODE ###

from bisect import bisect
N=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
B_reverse=B[::-1]
C=sorted(list(map(int,input().split())))
cnt=0
dict={}
val=0
for b in B_reverse:
    c_min=bisect(C,b)
    val+=N-c_min
    dict[b]=val
for a in A:
    b_min=bisect(B,a)
    if b_min==N:
        pass
    else:
        cnt+=dict[B[b_min]]
print(cnt)
### BUGGY CODE ###

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

check=[False]*n
ans=[[0 for i in range(n)]for j in range(n)]

from collections import deque

q=deque()
q.append(0)
num=[0]*n
num[0]=12345678
ma=1
while(q):
	node = q.pop()
	iro=1
	for next in g[node]:
		if num[next]!=0:
			continue
		if iro == num[node]:
			iro+=1
		ans[node][next] = iro
		ans[next][node] = iro
		num[next]=iro
		ma=max(ma,iro)
		q.append(next)
		iro+=1

print(ma)

for i in range(n-1):
	print(ans[ab[i][0]][ab[i][1]])


### FIXED CODE ###

from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from fractions import Fraction
import sys

N, *AB = map(int, sys.stdin.buffer.read().split())

dict_F = {}
count_0 = 0

def insert(A,B,s): # A>=0, B>0, s=0or1
  if Fraction(A,B) not in dict_F.keys():
    dict_F[Fraction(A,B)] = [0,0]
  dict_F[Fraction(A,B)][s] += 1

def make_power2(N):
  result = 1
  list_result = [1]
  for _ in range(N):
    result = (2*result)%mod
    list_result.append(result)
  return list_result

for i in range(N):
  A,B = AB[2*i], AB[2*i+1]
  if A==0 and B==0:
    count_0 += 1
  elif A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
power2 = make_power2(N)
answer = 1

for A,B in dict_F.values():
  answer = (answer*(power2[A]+power2[B]-1))%mod
answer = (answer+count_0-1)%mod

print(answer)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from math import gcd

N, *AB = map(int, sys.stdin.buffer.read().split())

dict_F = {}
count_0 = 0

def insert(A,B,s): # A>=0, B>0, s=0or1
  if (A,B) not in dict_F.keys():
    dict_F[(A,B)] = [0,0]
  dict_F[(A,B)][s] += 1

def make_power2(N):
  result = 1
  list_result = [1]
  for _ in range(N):
    result = (2*result)%mod
    list_result.append(result)
  return list_result

for i in range(N):
  A,B = AB[2*i], AB[2*i+1]
  if A==0 and B==0:
    count_0 += 1
    continue
  g = gcd(A,B)
  A //= g
  B //= g
  if A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
power2 = make_power2(N)
answer = 1

for A,B in dict_F.values():
  answer = (answer*(power2[A]+power2[B]-1))%mod
answer = (answer+count_0-1)%mod

print(answer)
### BUGGY CODE ###

from heapq import heappop as hpop
from heapq import heappush as hpush
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=1)
a+=[-99999999999999]
h=[]
for i in range(n):hpush(h,[-a[i]*2,i])
count=m
ans=0
while count!=0:
  x,i=hpop(h)
  x=-x
  c=min(count,1+(x!=a[i]*2))
  count-=c
  ans+=c*x
  x-=a[i]
  x+=a[i+1]
  i+=1
  hpush(h,[-x,i])
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):a[i]*=-1
a.sort()
from bisect import bisect_left,bisect_right
def check(mid):
  mm=0
  for i in range(n):
    if -(a[i]+a[0])<mid:break
    mm+=bisect_right(a,-(mid+a[i]))
  return mm
ok=0
ng=10**10+7
while ng!=ok+1:
  mid=(ok+ng)//2
  if check(mid)>=m:ok=mid
  else:ng=mid
b=[0]
for i in a:b.append(b[-1]+i)
ans=0
for i in range(n):
  if -(a[i]+a[0])<ok:break
  ind=bisect_right(a,-(ok+a[i]))
  ans+=a[i]*ind
  ans+=b[ind]
print(-(ans+(check(ok)-m)*ok))
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
mod = 10**9+7

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

step = [0] * (N+1)
step[0] = 1
step[1] = 1

for i in range(N+1):
    if i==0 or i==1:
        if i in A:
            step[i] = 0
    else:
        step[i] = step[i-1]+step[i-2]
        if i in A:
            step[i] = 0
        step[i] %= mod

print(step[-1])

### FIXED CODE ###

N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
mod = 10**9+7

step = [0] * (N+1)
step[0] = 1
step[1] = 1

for i in range(N+1):
    if i==0 or i==1:
        if i in A:
            step[i] = 0
    else:
        step[i] = step[i-1]+step[i-2]
        if i in A:
            step[i] = 0
        step[i] %= mod

print(step[-1])