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

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
X = N + M
sum_n = 0
sum_m = 0
ans = 0
for i in range(1,X+1):
    for j in range(i+1):
        n = j
        m = i - j
        if(n <= N and m <= M):
            sum_n = sum(A[0:n])
            sum_m = sum(B[0:m])
            if((sum_m + sum_n) <= K):
                ans=i
                sum_m = 0
                sum_n = 0
                break
            sum_m = 0
            sum_n = 0
print(ans)

### FIXED CODE ###

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a,b = [0],[0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])

ans,j = 0,M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans,i+j)
print(ans)
### BUGGY CODE ###

# YouTube
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)

def dfs(u):
    ok[u] = 1
    for v in to[u]:
        if ok[v]: continue
        dfs(v)

def rdfs(u):
    ok[u] += 2
    for v in fr[u]:
        if ok[v] > 1: continue
        rdfs(v)

inf = 10 ** 9
to = defaultdict(list)
fr = defaultdict(list)
abc = []
n, m, p = map(int, input().split())
ok = [0] * n
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    c = -(c - p)
    to[a].append(b)
    fr[b].append(a)
    abc.append([a, b, c])
dfs(0)
rdfs(n - 1)
score = [inf] * n
score[0] = 0
for i in range(n):
    stop = True
    for a, b, c in abc:
        if ok[a] < 3 or ok[b] < 3: continue
        tmp = score[a] + c
        if tmp < score[b]:
            score[b] = tmp
            stop = False
    if stop:
        print(max(0, -score[n - 1]))
        break
else:
    print(-1)


### FIXED CODE ###

# YouTube
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)

def dfs(u):
    ok[u] = 1
    for v in to[u]:
        if ok[v]: continue
        dfs(v)

def rdfs(u):
    ok[u] += 2
    for v in fr[u]:
        if ok[v] > 1: continue
        rdfs(v)

inf = 10 ** 9
to = defaultdict(list)
fr = defaultdict(list)
abc = []
n, m, p = map(int, input().split())
ok = [0] * n
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    c = -(c - p)
    to[a].append(b)
    fr[b].append(a)
    abc.append([a, b, c])
dfs(0)
rdfs(n - 1)
score = [inf] * n
score[0] = 0
for i in range(n):
    stop = True
    for a, b, c in abc:
        if ok[a] < 3 or ok[b] < 3: continue
        tmp = score[a] + c
        if tmp < score[b]:
            score[b] = tmp
            stop = False
    if stop:
        print(max(0, -score[n - 1]))
        break
else:
    print(-1)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    s = list(input()[:-1].decode())
    s.reverse()
    n = len(s)

    p10 = [0] * n
    p10[0] = 1
    for i in range(1, n):
        p10[i] = 10 * p10[i - 1]

    dp = [[0] * 13 for _ in range(n)]
    if s[0] == '?':
        for i in range(10):
            dp[0][i % 13] += 1
    else:
        dp[0][int(s[0]) % 13] += 1

    for i in range(1, n):
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][(k * p10[i] + j) % 13] += dp[i - 1][j] % mod
        else:
            for j in range(13):
                dp[i][(int(s[i]) * p10[i] + j) % 13] += dp[i - 1][j] % mod

    print(dp[-1][5] % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    s = list(input()[:-1].decode())
    n = len(s)

    dp = [0] * 13
    if s[0] == '?':
        for i in range(10):
            dp[i % 13] += 1
    else:
        dp[int(s[0]) % 13] += 1

    for i in range(1, n):
        tmp_dp = [0] * 13
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    index = (10 * j + k) % 13
                    tmp_dp[index] += dp[j]
                    tmp_dp[index] %= mod
        else:
            for j in range(13):
                index = (10 * j + int(s[i])) % 13
                tmp_dp[index] += dp[j]
                tmp_dp[index] %= mod
        dp = tmp_dp

    print(dp[5] % mod)


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

import bisect

n, q = map(int, input().split())
s = input()

ac_positions = []
for i in range(n):
    if s[i:i + 2] == 'AC':
        ac_positions.append(i + 1)

questions = []
for i in range(q):
    question = list(map(int, input().split()))


# for question in questions:
    ac_count = 0

    explore_ac_positions = ac_positions[
                           bisect.bisect_left(ac_positions, question[0]):
                           bisect.bisect_right(ac_positions, question[1] - 1)]

    ac_count = len(explore_ac_positions)
    # for ac_position in explore_ac_positions:
    #     if question[0] <= ac_position and ac_position + 1 <= question[1]:
    #         ac_count += 1

    print(ac_count)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
questions = [list(map(int, input().split())) for _ in range(q)]

ac_sum = [0]
for i in range(1, n + 1):
    ac_sum.append(ac_sum[i-1] + 1 if s[i-1 : i+1] == 'AC' else ac_sum[i-1])

for l, r in questions:
    print(ac_sum[r-1] - ac_sum[l-1])
### BUGGY CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)
    items = [(next(data), next(data)) for _ in range(N)]
    Q = next(data)

    H = min(N + 1, 1 << 10)
    Hb = (H - 1).bit_length()
    dp = [[0] * (MX + 1) for _ in range(H)]
    for i in range(1, H):
        v, w = items[i - 1]
        dpi = dp[i]
        dpip = dp[i >> 1]
        for j in range(w):
            dpi[j] = dpip[j]
        for j in range(w, MX + 1):
            dpi[j] = max(dpip[j], dpip[j - w] + v)

    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue
        ans = []
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    iv, iw = items[node - 1]
                    value += iv
                    weight += iw
                    if weight > L:
                        break
                node >>= 1
                i >>= 1
            else:
                ans.append(value + dp[node][L - weight])
        print(max(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)

    H = min(N + 1, 1 << 10)
    dp = [None] * H
    dp[0] = [0] * (MX + 1)
    IV, IW = [], []
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i >> 1][:]
            dp[i] = dpi
            for j in range(MX, w - 1, -1):
                dpi[j] = max(dpi[j], dpi[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

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

import numpy as np
import itertools
from math import factorial

N = int(input())

points = []
for i in range(0,N):
    points.append(list(map(int,input().split())))

p = itertools.permutations(points,N)

average = 0
for j in p:
    for k in range(0,len(j)-1):
        average += np.linalg.norm(np.array(j[k+1])-np.array(j[k]))

print('{:.10f}'.format(average/factorial(N)))

### FIXED CODE ###

from itertools import permutations
from math import factorial

N = int(input())

points = []
for i in range(0,N):
    points.append(list(map(int,input().split())))

p = permutations(points,N)

average = 0

for j in p:
    for k in range(0,len(j)-1):
        average += ((j[k+1][0] -j[k][0])**2 + (j[k+1][1] -j[k][1])**2)**0.5

print('{:.10f}'.format(average/factorial(N)))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
if n%2:
    flag = True
else:
    flag = False
for i in range(n):
    if (i+1)%2:
        b.append(a[i])
    else:
        b.insert(0,a[i])
if flag:
    print(*b[::-1])
else:
    print(*b)

### FIXED CODE ###

from collections import deque
n = int(input())
a = list(map(str, input().split()))
b = deque()
if n%2:
    flag = False
else:
    flag = True
for i in range(n):
    if flag:
        if (i+1)%2:
            b.append(a[i])
        else:
            b.appendleft(a[i])
    else:
        if (i+1)%2:
            b.appendleft(a[i])
        else:
            b.append(a[i])
res = list(b)
print(' '.join(res))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.insert(0, 0)
    b.insert(0, 0)
    ans = 0
    at = 0
    for i in range(n+1):
        at += a[i]
        if at > k:
            break
        bt = at
        for j in range(m+1):
            if bt + b[j] > k:
                break
            bt += b[j]
            if ans < i+j:
                ans = i+j
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

INF = 10**11


def main(input, print):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    at = [0] * (n+1)
    bt = [0] * (m+1)
    for i in range(1, n+1):
        at[i] = at[i-1]+a[i-1]
    for i in range(1, m+1):
        bt[i] = bt[i-1]+b[i-1]

    ans = 0
    j = m
    for i in range(n+1):
        if at[i] > k:
            break
        while k < at[i] + bt[j]:
            j -= 1
        ans = max(ans, i+j)

    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)
### BUGGY CODE ###

a,b,c,d = input().split()
a,b,c,d = int(a),int(b),int(c),int(d)
ad = []
for num in range(a,b+1):
    if num%c!=0:
        if num%d!=0:
            ad.append(num)

print(len(ad))

### FIXED CODE ###

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def lcm(a,b):
    return int(a*b//gcd(a,b))

def div(x,c,d):
    return x - x//c - x//d + x//lcm(c,d)


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

a = div(a-1,c,d)
b = div(b,c,d)
num = b-a

print(num)
### BUGGY CODE ###

s=input()
n=len(s)
mod=10**9+7
dp=[ [0]*3 for _ in range(n)]
#dp[i][0] count of A's in all possible strings u generate till i
#dp[i][1] count of AB's ''
#dp[i][2] count of ABC's ''
cnt=1
for i in range(n):
    if s[i]=='?':
        if i>0:
            dp[i][2]=dp[i-1][1]+3*dp[i-1][2]
            dp[i][1]=dp[i-1][0]+3*dp[i-1][1]
            dp[i][0]=3*dp[i-1][0]+1*cnt
        else:
            dp[i][0]=1
        cnt*=3
        cnt%=mod
    elif s[i]=='C':
        if i>0:
            dp[i][2]=dp[i-1][1]+dp[i-1][2]
            dp[i][1]=dp[i-1][1]
            dp[i][0]=dp[i-1][0]
    elif s[i]=='B':
        if i>0:
            dp[i][2]=dp[i-1][2]
            dp[i][1]=dp[i-1][0]+dp[i-1][1]
            dp[i][0]=dp[i-1][0]
    elif s[i]=='A':
        if i>0:
            dp[i][2]=dp[i-1][2]
            dp[i][1]=dp[i-1][1]
            dp[i][0]=dp[i-1][0]+1*cnt
        else:
            dp[0][0]=1

print(dp[-1][2]%mod)
            


### FIXED CODE ###

s=input()
n=len(s)
mod=10**9+7
dp=[ [0]*3 for _ in range(n)]
#dp[i][0] count of A's in all possible strings u generate till i
#dp[i][1] count of AB's ''
#dp[i][2] count of ABC's ''
cnt=1
for i in range(n):
    if s[i]=='?':
        if i>0:
            dp[i][2]=dp[i-1][1]+3*dp[i-1][2]
            dp[i][2]%=mod
            dp[i][1]=dp[i-1][0]+3*dp[i-1][1]
            dp[i][1]%=mod
            dp[i][0]=3*dp[i-1][0]+1*cnt
            dp[i][0]%=mod
        else:
            dp[i][0]=1
        cnt*=3
        cnt%=mod
    elif s[i]=='C':
        if i>0:
            dp[i][2]=dp[i-1][1]+dp[i-1][2]
            dp[i][2]%=mod
            dp[i][1]=dp[i-1][1]
            dp[i][0]=dp[i-1][0]
    elif s[i]=='B':
        if i>0:
            dp[i][2]=dp[i-1][2]
            dp[i][1]=dp[i-1][0]+dp[i-1][1]
            dp[i][1]%=mod
            dp[i][0]=dp[i-1][0]
    elif s[i]=='A':
        if i>0:
            dp[i][2]=dp[i-1][2]
            dp[i][1]=dp[i-1][1]
            dp[i][0]=dp[i-1][0]+1*cnt
            dp[i][0]%=mod
        else:
            dp[0][0]=1

print(dp[-1][2]%mod)
### BUGGY CODE ###

n = int(input())
A = list(input())
sumC = []

for i in range(n):
    countW = 0
    countE = 0
    for j in range(0, i):
        if A[j] == 'W':
            countW += 1
    for k in range(i + 1, n):
        if A[k] == 'E':
            countE += 1
    sumC.append(countW + countE)

print(min(sumC))

### FIXED CODE ###

n = int(input())
S = input()
ans = n
temp = 0

for i in range(1, n):
    if S[i] =='E':
        temp += 1
ans = min(ans, temp)

for i in range(1, n):
    if S[i - 1] == 'W':
        temp += 1
    if S[i] == 'E':
        temp -= 1
    ans = min(ans, temp)        

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

def main():
    n = int(input())
    a = [int(s) for s in input().split()]

    count = 0

    a_count = a.count

    for j in range(1, n):
        for i in range(j):
            if a_count(a[i]) >= 2:
                count += 1
                break

    if count >= 1:
        print('NO')
    else:
        print('YES')

if __name__ == '__main__':
    main()

### FIXED CODE ###

def has_duplicates(seq):
    return len(seq) != len(set(seq))

n = int(input())
a = [int(s) for s in input().split()]

if has_duplicates(a) == False:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

N, M = list(map(int, input().split()))
A = list([0] * N)   # A yen
B = list([0] * N)   # B hon
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))

bought = 0
price = 0
while(M > bought):
#    print("bought = {}, price = {}".format(bought, price))
    minidx = A.index(min(A))
#    print("found idx = " + str(minidx))
    if(M - bought >= B[minidx]):
#        print("buy = {}, price = {}".format(B[minidx], A[minidx]))
        price = price + A[minidx] * B[minidx]
        bought = bought + B[minidx]
        del A[minidx]
        del B[minidx]
    elif(M - bought < B[minidx]):
#        print("buy = {}, price = {}".format(M - bought, A[minidx]))
        price = price + A[minidx] * (M - bought)
        bought = M
        break

print(price)


### FIXED CODE ###

YEN = 0
NUM = 1

N, M = list(map(int, input().split()))
shop = list([])
for i in range(N):
    a, b = list(map(int, input().split()))
    shop.append([a, b])
shop.sort()

require = M
price = 0
minidx = 0
while(require > 0):
#    print("require = {}, price = {}".format(require, price))
#    print("idx = {}, num = {}, price = {}".format(minidx, shop[minidx][NUM], shop[minidx][YEN]))
    if(require >= shop[minidx][NUM]):
        price = price + shop[minidx][YEN] * shop[minidx][NUM]
        require = require - shop[minidx][NUM]
        minidx = minidx + 1
    else:
#        print("buy = {}, price = {}".format(require, A[minidx]))
        price = price + shop[minidx][YEN] * require
        require = 0

print(price)
### BUGGY CODE ###

import re
n,q=map(int,input().split())
s=input()
i=[p.span()[0] for p in re.finditer('(AC){1,1}',s)]
for _ in range(q):
  v=0
  l,r=map(int,input().split())
  a=list(range(l-1,r))
  for c in i:
    v+= c in a and c+1 in a
  print(v)

### FIXED CODE ###

import re
n,q=map(int,input().split())
s=input()
a=[0]*n
b=[0]*n
i=[p.span()[0]for p in re.finditer('(AC){1,1}',s)]
c=0
for m in range(n):
  if c>=len(i):
    if m<n-1:a[m+1]=a[m]
    b[m]=b[m-1]
    continue
  if m==i[c]:
    if m>0:
      if m<n-1:a[m+1]=a[m]+1
      b[m]=b[m-1]+1
    else:
      a[m]=0
      a[m+1]=1
      b[m]+=1
    c+=1
  else:
    a[m+1]=a[m]
    b[m]=b[m-1]
for _ in range(q):
  l,r=map(int,input().split())
  if l>=2:
    print(a[r-1]-b[l-2])
  else:
    print(a[r-1])
### BUGGY CODE ###

def main():
    N = int(input())
    table = [sorted(list(input())) for _ in range(N)]

    cnt = 0

    for i in range(N - 1):
        for j in range(i + 1, N):
            if table[i] == table[j]:
                cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections


def main():
    N = int(input())
    table = [''.join(sorted(list(input()))) for _ in range(N)]
    sort_table = set(table)
    cnt_table = collections.Counter(table)
    ans = 0
    for i in sort_table:
        num_of_i = cnt_table[i]
        if num_of_i <= 1:
            continue
        x = (num_of_i * (num_of_i - 1)) // 2
        ans += x

    print(ans)


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

N, M = map(int,input().split())
A = sorted(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]

for B, C in BC:
  B -= 1
  t = False
  if A[0] > C:
    continue
  while A[B] > C:
    B -= 1
    if B < 0:
      t = True
      break
  if t:
    continue
  if B == 0:
    A = [C] + A[1:]
  else:
    A = [C]*len(A[:B+1]) + A[B+1:]
  A.sort()
print(sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key = lambda x: -x[1])

for B, C in BC:
  A.extend([C]*B)
  if len(A) > N*2:
    break
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline().rstrip())

A = [int(x) for x in stdin.readline().rstrip().split()]

a = 0
while a < N:  
  B = [elem for idx,elem in enumerate(A) if idx != a]
  B.sort()
  a += 1
  print(B[(N-1)//2])

### FIXED CODE ###

from sys import stdin
 
N = int(stdin.readline().rstrip())
 
A = [int(x) for x in stdin.readline().rstrip().split()]

B = sorted(A)
 
for i in range(N):  
  if A[i] < B[N//2]:
    print(B[N//2])
  else:
    print(B[N//2-1])
### BUGGY CODE ###

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


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


p=1
h=[]
go=0
for i in range(1,k+1):
    
    
    
    

    h.append(p)
    p=a[p-1]
    
    if p in h:
        j=h.index(p)
        amari=(k-i-1)%(i-j)
        p=h[j+amari]
        go=1
        break

if go==1:
    p=a[p-1]

print(p)


### FIXED CODE ###

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


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

ar=[-1 for i in range(n+1)]
p=1

go=0


for i in range(1,k+1):
    
    
    
    

    ar[p]=i-1
    p=a[p-1]
    
    if ar[p]>0:
        j=ar[p]
        amari=(k-i)%(i-j)
        
        go=1
        break

if go==1:
    p=ar.index(j+amari)
    
    


print(p)
### BUGGY CODE ###

s = input()
if len(s) <= 3:
  print(0)
  exit()

chk = [str((i+1)*2019) for i in range(100000)]
ans = 0
for i in chk:
    if s.count(i) > 0:
      ans += s.count(i[1:])
      k = i[0]
      for j in range(1,10):
        if j == int(k):
          continue
        ans -= s.count(str(j)+i[1:])
    
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input().strip()
if len(s) <= 3:
  print(0)
  exit()
c = 0
chk = [0]*2019
for i,si in enumerate(s[::-1]):
  c += int(si)*pow(10,i,2019)
  chk[c%2019] += 1
ans = chk[0]
for i in chk:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

from functools import reduce
N = int(input())
As = list(map(int,input().split()))
f = True
r = reduce(lambda x, y: x * y, As)

if 1000000000000000001 <= r:
  print("-1")
else:
  print(r)



### FIXED CODE ###

N = int(input())
As = list(map(int,input().split()))
c = int(As[0])
i = 0
f = True
if 0 in As:
  print("0")
else:
  for x in As:
    if i == 0:
      i += 1
      continue
    c = c * x 
    if 1000000000000000001 <= c:
      print("-1")
      f = False
      break
  if f:
    print(c)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
a = LIST()
for i in range(m):
    a.sort(reverse=True)
    a[0] //= 2
print(sum(a))

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import heapify, heappop, heappush
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
a = [-i for i in LIST()]
heapify(a)
for i in range(m):
    b = heappop(a)
    b = - (- b // 2)
    heappush(a, b)
print(-sum(a))
### BUGGY CODE ###

from math import inf
n,h=map(int,input().split())
l=[int(i) for i in input().split()]
dp=[inf]*n
dp[0]=0
dp[1]=abs(l[1]-l[0])
for i in range(2,n):
    for j in range(1,min(i,h)+1):
        dp[i]=min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))
print(dp[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    INF = 10**10
    DP = [INF]*N
    DP[0] = 0
    DP[1] = abs(h[1]-h[0])
    for i in range(2,N):
        DP[i] = min(DP[i-j] + abs(h[i-j]-h[i]) for j in range(1,min(K,i)+1))
    print(DP[-1])
    
if __name__ == "__main__":
    main()