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

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
if K >= sum(A):
  print(0)
  exit()
A.sort(reverse=True)
F.sort()
from math import gcd
def lcm(x, y):
  return (x*y)//gcd(x, y)

f_lcm = 1
for k in range(N):
  f_lcm = lcm(f_lcm, F[k])

portion = [f_lcm//F[k] for k in range(N)]
sp = sum(portion)

#print('A:', A)
#print('F:', F)
#print('portion:', portion)
lot = [0 for _ in range(N)]


sa = sum(A) - K
for k in range(N):
  point = sa*portion[k]//sp
  if A[k] == 0:
    continue
  elif point > A[k]:
    lot[k] += A[k]*F[k]
    A[k] = 0
  else:
    lot[k] += point *F[k]
    A[k] -= point
res = sum(A) - K
#print(lot)
#print(A)
#print(res)

while res>0:
  second  = float('inf')
  for k in range(N):
    if A[k] > 0:
      second = min(second, lot[k] + F[k])
  for k in range(N):
    if A[k] > 0:
      if second == lot[k] + F[k]:
        lot[k] += F[k]
        A[k] -= 1
        res -= 1
  if res <0:
    break
  sa = sum(A) - K
  for k in range(N):
    point = sa*portion[k]//sp
    if A[k] == 0:
      continue
    elif point > A[k]:
      lot[k] += A[k]*F[k]
      A[k] = 0
    else:
      lot[k] += point *F[k]
      A[k] -= point
  res = sum(A) - K

print(max(lot))

### FIXED CODE ###

from math import ceil
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
if K >= sum(A):
  print(0)
  exit()
A.sort(reverse=True)
F.sort()
lot = []
for k in range(N):
  lot.append((A[k]*F[k], k))
lot.sort(key =  lambda x:x[0],reverse=True)
high = lot[0][0]
#print('A:', A)
#print('F:', F)
#rint(lot)
def binary_search(high):
  low = 0
  mid = (low + high) //2
  while low < high:
    final = False
    mid = (low + high) //2
    #print(low, high, mid)
    if low == high-1:
      final = True
    #print(low, high, mid)
    res = K
    flag = True
    for k in range(N):
      if res < 0:
        break
      else:
        if lot[k][0] <= mid:
          break
        else:
          res -= ceil((lot[k][0]-mid)/F[lot[k][1]])
          continue
    if res < 0:
      flag = False
    #print(flag)
    if flag:
      high = mid
    else:
      if final:
        mid += 1
      low = mid
    #print(low, high, mid)
  #return None
  return mid

print(binary_search(high))
### BUGGY CODE ###

from collections import Counter

N =int(input())
A_n =list(map(int,input().split()))
Q =int(input())
B_n ,C_n=[],[]
for i in range(Q):
    B,C =map(int,input().split())
    B_n.append(B)
    C_n.append(C)

sum0 =sum(A_n)
for i in range(Q):
    count =Counter(A_n)[B_n[i]]
    sum0 += (C_n[i]-B_n[i])*count
    A_n  =list(filter(lambda x: x != B_n[i] ,A_n))
    A_n.extend([C_n[i] for j in range(count)])
    print(sum0)
    

### FIXED CODE ###

from collections import Counter

N =int(input())
A_n =list(map(int,input().split()))
Q =int(input())
B_n ,C_n=[],[]
for i in range(Q):
    B,C =map(int,input().split())
    B_n.append(B)
    C_n.append(C)

dic =Counter(A_n)

sum0 =sum(A_n)
for i in range(Q):
    count = dic[B_n[i]]
    sum0 += (C_n[i]-B_n[i])*count
    dic[B_n[i]] = 0
    dic[C_n[i]] += count
    print(sum0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    ll.append(sum([min(x, i) for i in l]) / x)

for K in range(M):
    maximum_operation[K] = N-bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
### BUGGY CODE ###

n = int(input())
A = [int(i) * 2 for i in input().split()]
assert len(A) == n
S = sum(A) // 2
A += A
for i in range(n):
    ans = S
    for j in range(i + 1, i + n, 2):
        ans -= A[j]
    print(ans, end=' ')
print()

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]
assert len(A) == n
S = sum(A)
ans = S
for i in range(1, n, 2):
    ans -= A[i] * 2
print(ans, end=' ')
for i in range(1, n):
    ans = A[i - 1] * 2 - ans
    print(ans, end=' ')
print()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = [s for s in input()]
    _ = int(input())
    K = [int(i) for i in input().split()]

    def solve(k):
        cnt = {'D': 0, 'M': 0, 'DM': 0}
        ans = 0
        for i in range(N):
            if S[i] == 'D':
                cnt['D'] += 1
            elif S[i] == 'M':
                cnt['M'] += 1
                cnt['DM'] += cnt['D']
            elif S[i] == 'C':
                ans += cnt['DM']
            if k - 1 <= i:
                if S[i-k+1] == 'D':
                    cnt['DM'] -= cnt['M']
                    cnt['D'] -= 1
                if S[i-k+1] == 'M':
                    cnt['M'] -= 1
        return ans

    for k in K:
        print(solve(k))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = input()
    _ = int(input())
    K = [int(i) for i in input().split()]

    def solve(k):
        cd = 0
        cm = 0
        cdm = 0
        ans = 0
        for i in range(N):
            if S[i] == 'D':
                cd += 1
            elif S[i] == 'M':
                cm += 1
                cdm += cd
            elif S[i] == 'C':
                ans += cdm
            if k - 1 <= i:
                if S[i-k+1] == 'D':
                    cdm -= cm
                    cd -= 1
                if S[i-k+1] == 'M':
                    cm -= 1
        return ans

    for k in K:
        print(solve(k))


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

n = int(input())
A = []
cnt = 0
for i in range(n):
    m = input()
    if m in A:
        pass
    else:
        A.append(m)
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
A = [input() for i in range(n)]
print(-len(A) + len(set(A)) + n)
### BUGGY CODE ###

n=int(input())
a=0
for i in range(1,n+1):
    s=[]
    if "3" in str(i) and "5" in str(i) and "7" in str(i):
        for j in str(i):
            s.append(j)
        if len(set(s)) == 3:
                a+=1
print(a)


### FIXED CODE ###

n=int(input())

def dfs(s):
    if int(s)>n:
        return 0
    if all(s.count(c)>0 for c in "753"):
        a=1
    else:
        a=0

    for c in "753":
        a=a+dfs(s+c)

    return a

print(dfs("0"))
### BUGGY CODE ###

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

dp = [float('inf')] * N
dp[0] = 0

for i in range(N):
    for j in range(1,K+1):
        if (i+j < N):
            dp[i+j]=min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))

print(dp[N-1])


### FIXED CODE ###

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

dp = [float('inf')] * N
dp[0] = 0

for i in range(N):
    for j in range(1,K+1):
        if (i+j < N):
            dp[i+j]=min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))

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

n = int(input())
s = input()

ans = 0
maxi = n // 2
for i in range(maxi, 0, -1):
    dic = {}
    for j in range(n-i+1):
        if s[j:j+i] in dic.keys():
            if dic[s[j:j+i]] < j:
                print(i)
                exit()
        dic[s[j:j+i]] = j+i-1
print(ans)

### FIXED CODE ###

def z_algorithm(s):
    n = len(s)
    z = [0 for i in range(n)]
    z[0] = n
    i, j = 1, 0
    while i < n:
        while i+j < n and s[j] == s[i+j]:
            j += 1
        z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while k < j and k + z[k] < j:
            z[i+k] = z[k]
            k += 1
        i += k
        j -= k
    return z

n = int(input())
s = input()

ans = 0
for i in range(n):
    z = z_algorithm(s[i:])
    for j in range(len(z)):
        if z[j] <= j:
            ans = max(ans, z[j])
print(ans)
### BUGGY CODE ###

a,b = map(int,input().split())
ans = 1
for i in range(a,b+1):
  ans *= i
if ans > 0:
  print("Positive")
elif ans < 0:
  print("Negative")
elif ans == 0:
  print("Zero")

### FIXED CODE ###

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

if (a <= 0 and b >= 0) or (a==0) or (b==0):
  print("Zero")
elif (a > 0) or (b<0 and (b-a)%2==1):
  print("Positive")
elif (b<0 and (b-a)%2==0):
  print("Negative")
### BUGGY CODE ###

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

dp=[[0 for i in range(K+1)] for j in range(N)]

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

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

print(dp[N-1][K])

### FIXED CODE ###

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

dp=[[0 for i in range(K+1)] for j in range(N)]

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

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

print(dp[N-1][K])
### BUGGY CODE ###

import copy

N = int(input())

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

B = copy.copy(A)

for i in range(len(A)):
    A[i] = 0
    print(max(A))
    A[i] = B[i]


### FIXED CODE ###

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    max1st = max(A)
    max1stIndex = A.index(max1st)

    for i in range(len(A)):
        if i == max1stIndex:
            tmp = A[i]
            A[i] = 0
            print(max(A))
            continue

        print(max1st)




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

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

import sys
import os

N = 50001
lst = [True] * N
lst[0] = False
lst[1] = False
for i in range(2, int(N ** 0.5) + 1):
    if lst[i]:
        for j in range(2 * i, N, i):
            lst[j] = False

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break
    elif n % 2 == 1:
        if lst[n - 2]:
            print(1)
        else:
            print(0)
    elif n == 4:
        print(1)
    else:
        counter = 0
        for i in range(1, n // 2 + 1, 2):
            prime0 = i
            prime1 = n - i
            if prime0 <= prime1 and lst[prime0] and lst[prime1]:
                #print(prime0, prime1)
                counter += 1
        print(counter)

### FIXED CODE ###

import sys

N = 50001
lst = [True] * N
lst[0] = False
lst[1] = False
for i in range(2, int(N ** 0.5) + 1):
    if lst[i]:
        for j in range(i * i, N, i):
            lst[j] = False

primes = [i for i in range(1, N) if lst[i]]

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break
    elif n % 2 == 1:
        if lst[n - 2]:
            print(1)
        else:
            print(0)
    elif n == 4:
        print(1)
    else:
        counter = 0
        for prime0 in primes:
            prime1 = n - prime0
            if prime0 <= prime1 and lst[prime1]:
                #print(prime0, prime1)
                counter += 1
        print(counter)
### BUGGY CODE ###

import math
from functools import reduce
N = int(input())
A = list(map(int, input().split()))

def gcd_list(numbers):
  return reduce(math.gcd, numbers)

flag = False
for i in range(N-1):
  for j in range(i+1, N):
    if math.gcd(A[i], A[j]) != 1:
      flag = True
      break
  if flag:
    break
if not flag:
  print('pairwise coprime')
  exit()

b = gcd_list(A)
if b == 1:
  print('setwise coprime')
else:
  print('not coprime')

### FIXED CODE ###

import math
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
a = set()

def gcd_list(numbers):
  return reduce(math.gcd, numbers)

def prime_factorize(n):
  global a
  tmp = []
  while n % 2 == 0:
    if 2 not in a:
      tmp.append(2)
      n //= 2
    else:
      return False
  f = 3
  while f * f <= n:
    if n % f == 0:
      if f not in a:
        tmp.append(f)
        n //= f
      else:
        return False
    else:
      f += 2
  if n != 1:
    if n not in a:
      tmp.append(n)
    else:
      return False
  a |= set(tmp)
  return True

flag = True
for i in range(N):
  ans = prime_factorize(A[i])
  if not ans:
    flag = False
    break
if flag:
  print('pairwise coprime')
elif gcd_list(A) == 1:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

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

ans = 0

for k in range(60):
  cnt = [0] * 2
  for i in range(N):
    ans += cnt[(A[i] >> k & 1) ^ 1] << k
    cnt[A[i] >> k & 1] += 1

print(ans % (10 ** 9 + 7))



### FIXED CODE ###

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

ans = 0

for k in range(60):
  cnt = [0] * 2
  for i in range(N):
    ans += cnt[(A[i] >> k & 1) ^ 1] << k
    cnt[A[i] >> k & 1] += 1

print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

N,M = [int(s) for s in input().split()]
pre_lst=[]
for i in range(N):
  a,b = [int(s) for s in input().split()]
  pre_lst=pre_lst+[[a,b,a*b]]
lst = sorted(pre_lst, key=lambda x: x[0])
m=0
i=0
cost=0
while(m<M):
  m+=lst[i][1]
  cost+=lst[i][2]
  i+=1
if(m>M):
  cost-=lst[i-1][0]*(m-M)
print(cost)

### FIXED CODE ###

n, m = map(lambda x: int(x), input().split())
drinks = []
for _ in range(n):
    a, b = map(lambda x: int(x), input().split())
    drinks.append((a, b))
    
sorted_drinks = sorted(drinks, key=lambda x: x[0])

num_drinks = 0
sum_prices = 0
for price, num in sorted_drinks:
    num_drinks += num
    sum_prices += num * price
    if num_drinks > m:
        sum_prices -= (num_drinks - m) * price
        break
    elif num_drinks == m:
        break

print(sum_prices)
### BUGGY CODE ###

s = ' ' + input()
t = ' ' + input()

dp = [[0] * len(t) for _ in range(len(s))]
lcs = [[''] * len(t) for _ in range(len(s))]
for i in range(len(s)) :
    for j in range(len(t)) :
        if i == 0 or j == 0 :
            dp[i][j] = 0
            continue
            
        if s[i] == t[j] :
            dp[i][j] = dp[i-1][j-1] + 1
            lcs[i][j] = lcs[i-1][j-1] + s[i]
        else :
            if dp[i-1][j] >= dp[i][j-1] :
                dp[i][j] = dp[i-1][j]
                lcs[i][j] = lcs[i-1][j]
            else :
                dp[i][j] = dp[i][j-1]
                lcs[i][j] = lcs[i][j-1]

print(lcs[-1][-1])

### FIXED CODE ###

s = 'S' + input()
t = 'T' + input()

dp = [[0] * len(t) for _ in range(len(s))]
for i in range(len(s)) :
    for j in range(len(t)) :
        if i == 0 or j == 0 :
            continue
            
        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])
ret = ''
i, j = len(s)-1, len(t)-1
while i >= 1 and j >= 1 :
    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 ###

n, q = [int(elem) for elem in input().split()]
s = input()
new_s = [0]
for st1, st2 in zip(s[:-1], s[1:]):
    if st1 == "A" and st2 == "C":
        new_s.append(1)
    else:
        new_s.append(0)

out = []
for i in range(0, q):
    l, r = [int(elem) for elem in input().split()]
    out.append(sum(new_s[0:r]) - sum(new_s[0:l]))  

for elem in out:
    print(elem)

### FIXED CODE ###

n, q = [int(elem) for elem in input().split()]
s = input()
new_s = [0]
num = 0
for st1, st2 in zip(s[:-1], s[1:]):
    if st1 == "A" and st2 == "C":
        num += 1
        new_s.append(num)
    else:
        new_s.append(num)

out = []
for i in range(0, q):
    l, r = [int(elem) for elem in input().split()]
    out.append(new_s[r-1] - new_s[l-1])  

for elem in out:
    print(elem)
### BUGGY CODE ###

N=int(input())
B=[]
for i in range(N):
  s=input()
  s*=2
  B.append(s)
for i in range(N):
  B.append(B[i])

def solve(a,b):
  for i in range(N):
    for j in range(i+1,N):
      if B[a+i][b+j]!=B[a+j][b+i]:
        return False
  return True

ans=0
for i in range(N):
  if solve(i,0):
    ans+=N

print(ans)

### FIXED CODE ###

N=int(input())
S=[input() for _ in range(N)]

def solve(N,S):
  st=[tuple(x) for x in S]
  ch=list(zip(*st))
  ans=0
  for i in range(N):
    if st==ch:
      ans+=N
    st=st[-1:]+st[:-1]
    ch=[row[-1:] + row[:-1] for row in ch]
  return ans

print(solve(N,S))
### BUGGY CODE ###

n = int(input())
from collections import defaultdict as dd
dic = dd(lambda: 0)

counter = 0
for i in range(n):
  s = input()
  s_s = sorted(s)
  s_s_s = str(s_s)
  counter += dic[s_s_s]
  dic[s_s_s] += 1

print(counter)

### FIXED CODE ###

n = int(input())
from collections import defaultdict as dd
dic = dd(lambda: 0)

counter = 0
for i in range(n):
  s = input()
  s_s = sorted(s)
  s_s_s = "".join(s_s)
  counter += dic[s_s_s]
  dic[s_s_s] += 1

print(counter)
### BUGGY CODE ###

import numpy as np

N = int(input())

for n in range(1, N + 1):
    cnt = 0
    th = int(np.sqrt(n)) + 1
    for x in range(1, th):
        thy = int(np.sqrt(n - x ** 2)) + 1
        for y in range(1, x + 1):
            for z in range(1, y + 1):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    if x == y and y == z:
                        cnt += 1
                    elif x == y or y == z or z == x:
                        cnt += 3
                    else:
                        cnt += 1
    print(cnt)

### FIXED CODE ###

import numpy as np

N = int(input())
res = np.zeros(N+1)

th = int(np.sqrt(N)) + 1
for x in range(1, th):
    for y in range(1, x + 1):
        for z in range(1, y + 1):
            n = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if n > N:
                continue
            if x == y and y == z:
                res[n] += 1
            elif x == y or y == z or z == x:
                res[n] += 3
            else:
                res[n] += 6
for i in range(1, N+1):
    print(int(res[i]))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
	
for i in range(N):
	B = A[:]
	del B[i]
	B.sort(reverse = True)
	print(B[0])

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
B = sorted(A, reverse = True)

for i in range(N):
	if A[i] != B[0]:
		print(B[0])
	else:
		print(B[1])
### BUGGY CODE ###

from collections import defaultdict

N,M,Q=map(int,input().split())

Goal=[defaultdict(int) for _ in range(N)]
for i in range(M):
    L,R=map(int,input().split())
    Goal[L-1][R-1]+=1

Accumlate = [[0]*(N+1) for i in range(N)]
for g in range(N):
    for l in range(N):
        Accumlate[g][l+1]+=Accumlate[g][l]+Goal[g][l]

ans_list=[]
for l in range(Q):
    ans=0
    L,R=map(int,input().split())
    for l in range(L-1,R):
        ans+=Accumlate[l][R]-Accumlate[l][L-1]
    ans_list.append(ans)

for m in range(Q):
    print(ans_list[m])

### FIXED CODE ###

from collections import defaultdict

N,M,Q=map(int,input().split())

Goal=[defaultdict(int) for _ in range(N)]
for i in range(M):
    L,R=map(int,input().split())
    Goal[L-1][R-1]+=1

Accumlate = [[0]*(N+1) for i in range(N)]
for g in range(N):
    for l in range(N):
        Accumlate[g][l+1]+=Accumlate[g][l]+Goal[g][l]

ans_list=[]
for l in range(Q):
    ans=0
    L,R=map(int,input().split())
    for l in range(L-1,R):
        ans+=Accumlate[l][R]-Accumlate[l][L-1]
    ans_list.append(ans)

for m in range(Q):
    print(ans_list[m])
### BUGGY CODE ###

from sys import stdin, maxsize

def main():
    input = stdin.readline

    h, n = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    dp = [maxsize] * (h + 1)
    dp[0] = 0
    for i in range(h + 1):
        if dp[i] == maxsize:
            continue
        for x, y in a:
            if i + x < h and dp[i + x] > dp[i] + y:
                dp[i + x] = dp[i] + y
            elif i + x >= h and dp[h] > dp[i] + y:
                dp[h] = dp[i] + y
    print(dp[h])
main()

### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()
### BUGGY CODE ###

n,k=map(int,input().split())
h=[int(i) for i in input().split()]
li=[float('inf')]*(n)

li[0]=0
for i in range(1,n):
    for j in range(1,k+1):
        if i-j<0:
            continue
        li[i] = min(li[i],li[i-j]+abs(h[i]-h[i-j]))

print(li[-1])
    
    

### FIXED CODE ###

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

dp=[float('inf')]*n
dp[0]=0

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

N, M = map(int, input().split())
*S, = map(int, input().split())
*T, = map(int, input().split())

MOD = 10**9 + 7
P = []
for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            P.append((i, j))
P.sort(key=lambda x: (x[0], -x[1]))

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s % MOD
def add(k, x):
    while k <= M:
        data[k] = (data[k] + x) % MOD
        k += k & -k

s = 0
for p, q in P:
    v = get(q+1) + 1
    add(q+2, v); s += v
print((s + 1) % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
*S, = map(int, input().split())
*T, = map(int, input().split())

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s % MOD
def add(k, x):
    while k <= M:
        data[k] = (data[k] + x) % MOD
        k += k & -k

MOD = 10**9 + 7
s = 0
rM = range(M-1, -1, -1)
for i in range(N):
    si = S[i]
    for j in rM:
        if si == T[j]:
            v = get(j+1) + 1
            add(j+2, v); s += v
print((s + 1) % MOD)
### BUGGY CODE ###

ab=[]

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

for i in range(m):
    ab.append(tuple(map(int,input().split())))

ab.sort(key=lambda x:x[1])

res=0
index=0
toremove=set()
while(1):
    for j in range(index,len(ab)):
        if ab[index][1] < ab[j][0]:
          index=j
          res+=1
          break
    if index == len(ab):break

print(res)

### FIXED CODE ###

ab=[]

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

for i in range(m):
    ab.append(tuple(map(int,input().split())))

ab.sort(key=lambda x:x[1])

res=0
for z in range(len(ab)):
    x=ab[0][1]
    for j in range(len(ab)):
        if x > ab[0][0]:
            del ab[0]
        else:
            res+=1
            break
    if len(ab)==0:
        res+=1
        break
    
print(res)
### BUGGY CODE ###

n,m = map(int,input().split())
ls = list(map(int,input().split()))
di = [list(map(int,input().split())) for _ in range(m)]
for i in range(m):
    ls += [di[i][1]]*di[i][0]
ls.sort()
ls = ls[n*(-1):]
print(sum(ls))

### FIXED CODE ###

n,m = map(int,input().split())
ls = list(map(int,input().split()))
di = [list(map(int,input().split())) for _ in range(m)]
fi = []
for i,j in di:
    fi.append([j,i])
for k in ls:
    fi.append([k,1])
fi.sort(reverse=True)
ans = 0
cnt = 0
how = 0
while True:
    if how + fi[cnt][1] < n:
        how += fi[cnt][1]
        ans += fi[cnt][1]*fi[cnt][0]
    else:
        ans += (n-how)*fi[cnt][0]
        break
    cnt += 1
print(ans)