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

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [float('inf')] * n
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2,n):
    min_cost = float('inf')
    for j in range(1,min(i,k)+1):
        tmp = dp[i-j] + abs(h[i] - h[i-j])
        min_cost = min(min_cost, tmp)
    dp[i] = min_cost

print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [0] * n
dp[1] = abs(h[1] - h[0])

for i in range(2,n):
    min_cost = 999999999
    for j in range(1,min(i,k)+1):
        tmp = dp[i-j] + abs(h[i] - h[i-j])
        min_cost = min(min_cost, tmp)
    dp[i] = min_cost

print(dp[n-1])
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
dp = [0] * N
for i in range(1, N):
    dp[i] = min(dp[i-j] + abs(H[i] - H[i-j]) for j in range(1, min(i, K) + 1))
print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
dp = [0] * N
for i in range(1, N):
    dp[i] = min(dp[i-j] + abs(H[i] - H[i-j]) for j in range(1, min(i, K) + 1))
print(dp[-1])
### BUGGY CODE ###

import itertools
import collections

N,M=map(int,input().split())
L=list()
for i in range(M):
  a,b=map(int,input().split())
  A=list(range(a,b))
  L.append(A)
R=tuple(itertools.chain.from_iterable(L))
i=0
while True:
  L=[i for i in L if collections.Counter(R).most_common()[0][0] not in i]
  R=tuple(itertools.chain.from_iterable(L))
  i+=1
  if len(L)==0:
    break
print(i)

### FIXED CODE ###

N,M=map(int,input().split())
L=list()
for i in range(M):
  a,b=map(int,input().split())
  A=list([b,a])
  L.append(A)
L=sorted(L)
R=[L[0][0]-1]
for j in range(M):
  if R[-1] not in range(L[j][1],L[j][0]):
    R.append(L[j][0]-1)
print(len(R))
### BUGGY CODE ###

n,y=map(int,input().split())
flag=False
if 10000*n<y:
    print('-1 -1 -1')
elif 10000*n==y:
    print(str(n)+' 0 0')
else:
    for i in range(n+1):
        if flag:
            break
        for j in range(n+1):
            if flag:
                break
            for k in range(n+1):
                if 10000*i+5000*j+1000*k==y and i+j+k==n:
                    print(str(i)+' '+str(j)+' '+str(k))
                    flag=True
                    break
    if flag==False:
        print('-1 -1 -1')


### FIXED CODE ###

n,y=map(int,input().split())
flag=False
if 10000*n<y:
    print('-1 -1 -1')
elif 10000*n==y:
    print(n,0,0)
else:
    for i in range(n+1):
        if flag:
            break
        for j in range(n-i+1):
            if 10000*i+5000*j+1000*(n-i-j)==y:
                print(i,j,n-i-j)
                flag=True
                break
    else:
        print('-1 -1 -1')
### BUGGY CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for i in range(n-1,-1,-1):
    try:
        while True:
            if p<n:
                if a[i]+a[p]<=md: p+=1
                else: break
            else: break
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)


### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**9
dp = [INF]*n
dp[0] = 0

for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(
            dp[i],
            dp[j]+abs(h[i]-h[j])
        )
print(dp[-1])


### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**9
dp = [INF]*n
dp[0] = 0

for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(
            dp[i],
            dp[j]+abs(h[i]-h[j])
        )
print(dp[-1])
### BUGGY CODE ###

N = int(input())
city = []
for i in range(N):
  x,y,p = map(int,input().split())
  city.append((x,y,p))

xx = [ [ abs(city[j][0]) for j in range(N) ] for i in range(2<<N) ]
yy = [ [ abs(city[j][1]) for j in range(N) ] for i in range(2<<N) ]

for i in range(2<<N):
  X = [0]
  rest = []
  for j in range(N):
    if i>>j&1:
      X.append(city[j][0])
      xx[i][j] = 0
    else:
      rest.append(j)

  for j in rest:
    res = 10**15
    for k in X:
      res = min(res, abs(city[j][0]-k))
    xx[i][j] = res

for i in range(2<<N):
  Y = [0]
  rest = []
  for j in range(N):
    if i>>j&1:
      Y.append(city[j][1])
      yy[i][j] = 0
    else:
      rest.append(j)

  for j in rest:
    res = 10**15
    for k in Y:
      res = min(res, abs(city[j][1]-k))
    yy[i][j] = res


ans = [10**15 for _ in range(N+1)]
for i in range(2<<N):
  cond = i
  rest = [j for j in range(N) if i>>j&1==0]
  count = N-len(rest)

  while True:
    X = cond
    Y = i-cond
    temp = 0
    for j in rest:
      temp += min(xx[X][j], yy[Y][j])*city[j][2]
    ans[count] = min(ans[count], temp)
    if cond == 0:
      break
    else:
      cond = (cond-1)&i

for i in range(N+1):
  print(ans[i])


### FIXED CODE ###

N=int(input())
city=[]
for i in range(N):
    x,y,p=map(int,input().split())
    city.append((x,y,p))
 
xx=[[abs(city[j][0]) for j in range(N)] for i in range(2**N)]
yy=[[abs(city[j][1]) for j in range(N)] for i in range(2**N)]
 
for i in range(2**N):
    X=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            X.append(city[j][0])
            xx[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in X:
            res=min(res,abs(city[j][0]-k))
        xx[i][j]=res
 
for i in range(2**N):
    Y=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            Y.append(city[j][1])
            yy[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in Y:
            res=min(res,abs(city[j][1]-k))
        yy[i][j]=res
 
ans=[10**15 for i in range(N+1)]
for i in range(2**N):
    cond=i
    rest=[j for j in range(N) if i>>j &1==0]
    count=N-len(rest)
    while True:
        X=cond
        Y=i-cond
        temp=0
        for j in rest:
            temp+=min(xx[X][j],yy[Y][j])*city[j][2]
        ans[count]=min(ans[count],temp)
        if cond==0:
            break
        else:
            cond=(cond-1)&i
 
for i in range(N+1):
    print(ans[i])
### BUGGY CODE ###

# Widespread
n,a,b = list(map(int, input().split()))
h = []
for i in range(n):
    h.append(int(input()))

import numpy as np
import math as m

nh = np.array(h)

def testATK(ary, num, a, b):
    ary = np.array(ary)
    atk1 = b*num
    tmp = ary - atk1
    bommed = []
    for e in tmp:
        if(e>0):
            bommed.append(e)
    bommed = np.array(bommed)
    atk2 = a-b
    bomneed = list(map(m.ceil, (bommed/atk2)))
    acnt = np.sum(bomneed)
    if acnt > num:
        return "NO"
    else:
        return "YES"

imin = 1
imax = m.ceil(max(nh)/b)

def bs(ary, imin, imax):
    if (imax < imin):
        return imin
    else:
        imid = imin + (imax - imin)//2
        if (testATK(nh,imid,a,b)=="YES"):
            return bs(ary, imin, imid - 1)
        elif (testATK(nh,imid,a,b)=="NO"):
            return bs(ary, imid + 1, imax)
print(bs(nh, imin, imax))

### FIXED CODE ###

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

import math

sup = sum([hh // a + 1 for hh in h])
inf = 1
 
while sup - inf > 1:
    x = (sup + inf) // 2
    c = sum([math.ceil((hh - x * b)/(a-b)) for hh in h if hh > x * b])
    if c <= x:
        sup = x
    else:
        inf = x
 
print(sup)
### BUGGY CODE ###

n = int(input())
s = list(input() for i in range(n))
t = []
r = []

for i in range(n):
    if not s[i] in t:
        t.append(s[i])
        r.append(1)
    else:
        j = t.index(s[i])
        r[j] += 1

m = max(r)
z = []

for i in range(len(t)):
    if r[i] == m:
        z.append(t[i])

z.sort()

for i in range(len(z)):
    print(z[i])

### FIXED CODE ###

import collections

n = int(input())
s = list(input() for i in range(n))
s = sorted(s)
c = collections.Counter(s)
p = max(c.values())
s = sorted(list(set(s)))

for i in range(len(s)):
    if c[s[i]] == p:
        print(s[i])
### BUGGY CODE ###

from functools import reduce
N = int(input())

def up(n):
  global next_digit
  n += next_digit
  next_digit = 0
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    next_digit = 1
    return 0

digit = [0 for i in range(30)]
#a = [(digit[i] * (2 ** i)) for i in range(30)]
while True:
  a = [(digit[i] * ((-2) ** i)) for i in range(30)]
  #print(digit)
  #print(a)
  if sum(a) == N:
    break
  else:
    next_digit = 0
    digit[0] += 1
    for i in range(30):
      digit[i] = up(digit[i])
#print(digit)
rev_digit = [i for i in reversed(digit)]
result = reduce(lambda x, y:10*x+y, rev_digit)
print(result)

### FIXED CODE ###

N = int(input())
dig = []
def dmod(a, b):
  if a % b < 0:
    return [1, a//b+1]
  else:
    return [a%b, a//b]
while abs(N) > 1 :
  d, N = dmod(N, -2)
  dig.append(d)
if N == -1:
  dig += [1, 1]
else:
  dig.append(N)
dig.reverse()

n = ''.join(map(str, dig))
print(int(n))
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
count = 0
tof = True

for i in range(n):
  for j in range(i):
    if p[j] >= p[i]:
      continue
    else:
      tof = False
      continue
  if tof:
    count += 1
  else:
    tof = True
  
print(count)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
count = 0
m = [0] * n

memo = n
for i in range(n):
    if memo > p[i]:
        m[i] = p[i]
        memo = p[i]
    else:
        m[i] = memo

for i in range(1, n+1):
    if p[i-1] <= m[i-1]:
        count += 1

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

H,N=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

D=[1<<31]*(H+10**4)
D[0]=0

for hp in range(H):
    for a,b in M:
        D[hp+a]=min(D[hp+a],D[hp]+b)
print(min(D[H:]))

### FIXED CODE ###

H,N=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

D=[1<<31]*(H+10**4)
D[0]=0

for hp in range(H):
    for a,b in M:
        D[hp+a]=min(D[hp+a],D[hp]+b)
print(min(D[H:]))
### BUGGY CODE ###



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

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

ans = set([i for i in range(n)])


for i in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    if a in ans:
        if h[a] <= h[b]:
            ans = ans - {a}
    if b in ans:
        if h[b] <= h[a]:
            ans = ans - {b}

print(len(ans))


### FIXED CODE ###



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

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

# a = [0] * m
# b = [0] * m

ma = [0]*n


for i in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    ma[a] = max(ma[a],h[b])
    ma[b] = max(ma[b],h[a])

ans = 0    
for i in range(n):
    if h[i] > ma[i]:
        ans += 1
        

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

import sys
input=sys.stdin.readline
K,S=map(int,input().split());c=0
for x in range(K+1):
  if x>S:
    break
  for y in range(K+1):
    if x+y>S:
      break 
    for z in range(K+1):
      if x+y+z>S:
        break
      if x+y+z == S:
        c+=1
print(c)

### FIXED CODE ###

import sys
input=sys.stdin.readline
K,S=map(int,input().split());c=0
for x in range(K+1):
  for y in range(K+1):
    z = S-x-y
    if 0<=z<=K:
      c+=1
print(c)
### BUGGY CODE ###

import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
x_ = dp[0]
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        for v in range(10):
            w = 13 - v * now % 13
            x += np.hstack((x_[w:13], x_[:w]))
    else:
        v = 13 - int(s) * now % 13
        x += np.hstack((x_[v:13], x_[:v]))
    x %= mod
    now, pre = (now - pre) % 13, now
    x_ = x
print(int(dp[-1][5]))

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

n = int(input())
A = list(map(int, input().split()))
A.sort()

ans = 0
for x in set(A):
    tmp = [a for a in A if x-1 <= a <= x+1]
    ans = max(ans, len(tmp))

print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
c = [0]*100000
ans = 0
for a in A:
    c[a] += 1

for i in range(1, 99999):
    cnt = c[i-1] + c[i] +c[i+1]
    ans = max(ans, cnt)

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

n = int(input())
k = 1
for i in range(1,n+1):
  k = k*i
print(k%(10**9+7))


### FIXED CODE ###

n = int(input())
k = 1
for i in range(1,n+1):
  k = k*i%(10**9+7)
print(k)
### BUGGY CODE ###

H = int(input())

cnt = H
B = [H]
for i in range(1000000000):
    cnt = cnt//2
    B.append(cnt)
    if cnt == 1:
        break

C =[1]
for i in range(1,10000):
    C.append(C[i-1]*2)

ans= 0
for i in range(len(B)):
    ans +=C[i]
print(ans)


### FIXED CODE ###

H = int(input())
cnt = H
ans = 0
B = [H]

if H == 1:
    ans == 'NA'
else:
    for i in range(100000000000):
        cnt = cnt//2
        B.append(cnt)
        if cnt == 1:
            break

C =[1]
for i in range(1,1001):
    C.append(C[i-1]*2)

if ans == 'NA':
    print('0')
else:
    for i in range(len(B)):
        ans +=C[i]
print(ans)
### BUGGY CODE ###

def main():
    S = input()
    cnt = 0
    for i in range(len(S)):
        if S.find("10") != -1 or S.find('01') != -1:
            if S.find("10") != -1:
                S = S.replace("10", "", 1)
                cnt += 1
            if S.find("01") != -1:
                S = S.replace("01", "", 1)
                cnt += 1
        else:
            break
    print(cnt*2)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = input()
    print(2*min(S.count("0"), S.count("1")))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
lr = [[int(i) for i in input().split()] for i in range(Q)]

for i in lr:
    print(S[i[0]-1:i[1]].count("AC"))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
S = input()
lr = [[int(i) for i in input().split()] for i in range(Q)]
C = [0]*(N+1)
terget = "AC"
index = -1
for i in range(N):
    C[i+1] = C[i] + (S[i:i+2] == "AC")
for l,r in lr:
    print(C[r-1] - C[l-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n,x,y = map(int,input().split())

import queue
# FIFOキューの作成
q = queue.Queue()

dst = [10**18] * (n+1)

kyori = [0] * (n+1)
"""
for i in range(n):
    dst[i+1][i+1] = 0
"""
#num = 1

for i in range(1,n):
    #num = 1
    dst[i] = 0
    q.put([i,0])
    while not q.empty():
        
        kari = q.get()
        tmp = kari[0]
        tmp_dst = kari[1]
        #print(tmp[0])
        #exit()
        if tmp >= n+1:
            continue
        if tmp < 1:
            continue
        if tmp == x:
            if dst[y] == 10**18:
                #kyori[tmp_dst+1] += 1
                dst[y] = tmp_dst+1
                q.put([y,tmp_dst+1])
                
        if tmp == y:
            if dst[x] == 10**18:
                #kyori[tmp_dst+1] += 1
                dst[x] = tmp_dst+1
                q.put([x,tmp_dst+1])
        if tmp+1 <= n:
            if dst[tmp+1] == 10**18:
                q.put([tmp+1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[tmp+1] = tmp_dst+1
        if tmp-1 >= 1:
            if dst[tmp-1] == 10**18:
                q.put([tmp-1,tmp_dst+1])
                #kyori[tmp_dst+1] += 1
                dst[tmp-1] = tmp_dst+1
        
        #num += 1
        #print(dst[i])
    #exit()
    for j in range(i+1,n+1):
        kyori[dst[j]] += 1
    dst = [10**18] * (n+1)
"""
#print(kyori)
print(dst)
exit()

kyori = [0] * (n+1)

for i in range(1,n):
    #print(dst[i],i)
    for j in range(i+1,n+1):
        #print(i,j,dst[i][j])
        kyori[dst[i][j]] += 1
"""
#print(kyori)
#exit()

for i in range(1,n):
    print(kyori[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n,x,y = map(int,input().split())

dst = [0] * n

#print(dst)

for i in range(1,n+1):
    for j in range(i+1,n+1):
        kyori = min(j-i,abs(x-i)+abs(y-j)+1)
        dst[kyori] += 1
        #print(i,j,kyori)
        
for i in range(n-1):
    print(dst[i+1])
#print(dst)
### BUGGY CODE ###

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

for _ in range(m):
  maxvalue = max(a) 
  maxindex = a.index(maxvalue)
  a[maxindex] = maxvalue / 2

print(sum([int(_) for _ in a]))
  

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = [int(_) for _ in input().split()]
que = []
for _ in a:
  heapq.heappush(que, -1*_)

for _ in range(m):
  maxvalue = -1 * heapq.heappop(que)
  maxvalue /= 2
  heapq.heappush(que, -1*maxvalue)

print(sum([int(-1*_) for _ in que]))
### BUGGY CODE ###

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

ans = [n*(n-1)//2]
remains = set(range(1, n+1))
sets = []
for i in range(m-1):
    a, b = ab[-(i+1)]
    if a in remains and b in remains:
        sets.append(set([a, b]))
        remains.remove(a)
        remains.remove(b)
        ans.append(ans[i] - 1)
    elif a not in remains and b in remains:
        for i_set in range(len(sets)):
            if a in sets[i_set]:
                size_a = len(sets[i_set])
                sets[i_set].add(b)
                remains.remove(b)
                ans.append(ans[i] - size_a)
                break
    elif a in remains and b not in remains:
        for i_set in range(len(sets)):
            if b in sets[i_set]:
                size_b = len(sets[i_set])
                sets[i_set].add(a)
                remains.remove(a)
                ans.append(ans[i] - size_b)
                break
    else:
        i_set_a, i_set_b = None, None
        for i_set in range(len(sets)):
            if a in sets[i_set]:
                i_set_a = i_set
                size_a = len(sets[i_set])
            if b in sets[i_set]:
                i_set_b = i_set
                size_b = len(sets[i_set])
            if i_set_a is not None and i_set_b is not None:
                break
        if i_set_a == i_set_b:
            ans.append(ans[i])
        else:
            sets[i_set_a] = sets[i_set_a].union(sets[i_set_b])
            sets.pop(i_set_b)
            ans.append(ans[i] - size_a*size_b)
    # print(sets, remains)

for a in ans[::-1]:
    print(a)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)][::-1]

par, sizes = [-1]*(n+1), [1]*(n+1)
def find(i):
    if par[i] < 0:
        return i
    else:
        par[i] = find(par[i])
        return par[i]

ans = [n*(n-1)//2]
for i in range(m-1):
    a, b = ab[i]
    pa, pb = find(a), find(b)

    if pa != pb:
        ans.append(ans[i] - sizes[pa]*sizes[pb])
        par[pa] = pb
        sizes[pb] += sizes[pa]
    else:
        ans.append(ans[i])
    # print(par, sizes)

for ans_ in ans[::-1]:
    print(ans_)
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
aa=sorted(a,reverse=True)
bb=sorted(b,reverse=True)
cc=sorted(c,reverse=True)
n=0
l=[]
while n<=k:
    for i in range(k//3):
        for j in range(k//3):
            for x in range(k//3):
                ll=l.append(aa[i]+bb[j]+cc[x])
ll.sort(reverse=True)
for i in range(k):
    print(ll[i])

### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=sorted(list(map(int,input().split())),reverse=True)
ab=[]
for i in a:
    for j in b:
        ab.append(i+j)
ab.sort(reverse=True)
ans=[]
for i in range(min(k,len(ab))):
    for j in range(min(k,len(c))):
        ans.append(ab[i]+c[j])
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

n,k=map(int,input().split())
H=list(map(int,input().split()))
A=[float("inf")]*n
A[0]=0
for i in range(1,n):
  if i<=k:
    A[i]=min(A[i-j]+abs(H[i]-H[i-j]) for j in range(1,i+1))
  else:
    A[i]=min(A[i-j]+abs(H[i]-H[i-j]) for j in range(1,k+1))
print(A[n-1])

### FIXED CODE ###

def solve():
  n,k=map(int,input().split())
  H=list(map(int,input().split()))
  A=[0]*n
  for i in range(1,n):
    A[i]=min(A[i-j]+abs(H[i]-H[i-j]) for j in range(1,min(i+1,k+1)))
  return A[n-1]
print(solve())
### BUGGY CODE ###

N = int(input())
A = list()
for _ in range(N):
    A.append(int(input()))

for i in range(N):
    rem = A[i]
    A.remove(rem)
    print(max(A))
    A.insert(i, rem)


### FIXED CODE ###

import copy

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

result = max(A)
ind = A.index(result)

for i in range(N):
    if i == ind:
        a = copy.deepcopy(A)
        a.remove(result)
        print(max(a))
    else:
        print(result)
### BUGGY CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
e = [0.0] * n
for i in range(n):
    e[i] = (1 + p[i]) * 0.5
s = 0.0
for i in range(k, n + 1):
    t = sum(e[i - k:i])
    if s < t:
        s = t
print(s)


### FIXED CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
e = [(1 + p[i]) * 0.5 for i in range(n)]
s = 0.0
for i in e[:k]:
    s += i
t = s
for i in range(n - k):
    t = t - e[i] + e[k + i]
    s = max(s, t)
print(s)
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0,~z;i,j=s//w+y[x],s%w+y[x+1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

import itertools

n, k = map(int, input().split())
S = input()
blocks = [(k, len(list(v))) for k, v in itertools.groupby(S)]
res = 0
for i in range(len(blocks)):
  if blocks[i][0] == '0':
    res = max(res, sum([b[1] for b in blocks[i:i+2*k]]))
  else:
    res = max(res, sum([b[1] for b in blocks[i:i+2*k+1]]))
print(res)

### FIXED CODE ###

import itertools
 
_, k = map(int, input().split())
S = input()
blocks = [(key, len(list(v))) for key, v in itertools.groupby(S)]
res = 0
i = 0
if blocks[i][0] == '0':
  res = max(res, sum([b[1] for b in blocks[i:i+2*k]]))
  i += 1

crr = sum([b[1] for b in blocks[i:i+2*k+1]])
res = max(res, crr)
while i+2*k + 2 < len(blocks):
  i += 2
  crr = crr + blocks[i+2*k-1][1] + blocks[i+2*k][1]
  crr = crr - blocks[i-1][1] - blocks[i-2][1]
  res = max(res, crr)

crr = sum([b[1] for b in blocks[-2*k:]])
res = max(res, crr)
print(res)