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

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
for i in range(0,m):
    b,c = map(int,input().split())
    for j in range(0,b):
        if a[j]<c:
            a[j] = c
        else:
            break
    a.sort()
print(sum(a))

### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
bc = []
for i in range(0,m):
    temp_bc = list(map(int,input().split()))
    bc.append(temp_bc)
bc.sort(key=lambda x:x[1])
bc.reverse()
i = 0
for j in range(0,m):
    for k in range(0,bc[j][0]):
        if a[i] < bc[j][1]:
            a[i] = bc[j][1]
        i += 1
        if i == n:
            break
    if i == n:
        break

print(sum(a))
### BUGGY CODE ###

import bisect
n,k = map(int, input().split())
x = list(map(int, input().split()))
z = bisect.bisect_left(x,0)

ans=10**12
s=z-k+1
if s < 0:
  s=0
if z == 0:
  z+=1
for i in range(s,z):
  t=x[i:i+k]
  xl=min(t)
  xr=max(t)
  ans=min(ans,abs(xr)+abs(xr-xl),abs(xl)+abs(xr-xl))
print(ans)

### FIXED CODE ###

import bisect
n,k = map(int, input().split())
x = list(map(int, input().split()))
z = bisect.bisect_left(x,0)

ans=10**12
s=z-k
if s < 0:
  s=0
g=z+1
if g+k >= n:
  g=n-k+1
for i in range(s,g):

  xl=x[i]
  xr=x[i+k-1]
  ans=min(ans,abs(xr)+abs(xr-xl),abs(xl)+abs(xr-xl))
print(ans)
### BUGGY CODE ###

K = int(input())
A = 7 % K 

if K % 2 == 0:
    print(-1)
    exit()

for i in range(1, K + 1):
    if A % K == 0:
        print(i)
        exit()
    A = 10 * A + 7


### FIXED CODE ###

K = int(input())
ans = -1
N = 7
for i in range(K):
    if N % K == 0:
        ans = i+1
        break
    N = (N*10+7) % K
print(ans)
### BUGGY CODE ###

S = input()
end = len(S) // 2
for i in range(end):
    S = S.replace("ST","")

print(len(S))


### FIXED CODE ###

X = input()
N = len(X)
S = 0
ans = 0
for i in range(N):
    if X[i] == 'S':
        S += 1
    elif S > 0:
        S -= 1
        ans += 2
        
print(N - ans)
### BUGGY CODE ###

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

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

cf_li = cf(x,y)

def sieve_of_eratosthenes(li):
    for i in li:
        li = [x for x in li if (x == i or x % i != 0)]
    return li

ans_li = sieve_of_eratosthenes(cf_li)

print(len(ans_li) + 1)

### FIXED CODE ###

import math
import fractions

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

gcd = fractions.gcd(x,y)

size = int(math.sqrt(gcd)) + 1

def calc_div(num):
    table =  []
    for i in range(2,int(math.sqrt(num))+1):
        if num % i == 0:
            table.append(i)    
            while num % i == 0:
                num //= i
    if num > int(math.sqrt(num)):
        table.append(num)
    return table 

ans = calc_div(gcd)

print(len(ans) + 1)
### BUGGY CODE ###

from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
N1097 = 10**9 + 7

def main():
    N = ii()
    A = lmis()
    l = 1
    for a in A:
        l = lcm(l, a)
    ans = 0
    for a in A:
        ans += l//a
        ans %= N1097
    print(ans)


main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    A = lmis()
    l = 1
    for a in A:
        l = lcm(l, a)
    print(sum(l//a for a in A) % N1097)


main()
### BUGGY CODE ###

#input
s = input()
t = input()

#output
def lcs(s, t):
    m = len(s)
    n = len(t)
    matrix = [["" for x in range(n)] for x in range(m)]
    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                if i == 0 or j == 0:
                    matrix[i][j] = s[i]
                else:
                    matrix[i][j] = matrix[i-1][j-1] + s[i]
            else:
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1], key=len)

    cs = matrix[-1][-1]

    return cs

print(lcs(s, t))

### FIXED CODE ###

#input
s = input()
t = input()

#output
m = len(s)
n = len(t)
dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(n):
    for j in range(m):
        if t[i] == s[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

ans = ""
while m > 0 and n > 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    elif dp[n][m] == dp[n-1][m-1] + 1:
        ans += t[n-1]
        n -= 1
        m -= 1

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

n, *a = map(int, open(0).read().split())
b = []
for i in range(n):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.insert(0, a[i])

if n % 2 == 0:       
    print(' '.join(map(str, b)))
else:
    print(' '.join(map(str, b[::-1])))

### FIXED CODE ###

n, *a_l = map(int, open(0).read().split())
b = []

for a in a_l[::-2]:
        b.append(a)
for a in a_l[n%2::2]:
        b.append(a)

print(' '.join(map(str, b)))
### BUGGY CODE ###

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

flag = True
if N < M:
  flag = False
else:
  for t in T:
    if t in D:
      D.remove(t)
    else:
      flag = False
      break
    
if flag:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

from collections import Counter
N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))

c = Counter(D)
flag = True
for t in T:
  if c[t] > 0:
    c[t] -= 1
  else:
    flag = False
    break
    
if flag:
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

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

ans = 0
for h in range(k+1):
    for i in range(k+1):
        for j in range(k+1):
            if h+i+j ==s:
                ans += 1
print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(k+1):
    for j in range(k+1):
        if k >= s-i-j >= 0: 
            ans += 1
print(ans)
### BUGGY CODE ###

s = input()
S = [int(s[i]) for i in range(len(s))]
# print(S)
count = 0
while 1:
    #print("S:", S)
    is_continue = False
    # print(len(S))
    for i in range(len(S) - 1):
        #print(S[i], S[i+1])
        if S[i] != S[i + 1]:
            # print(count)
            del S[i]
            del S[i]
            count += 2
            is_continue = True
            break
    if not is_continue:
        break
print(count)


### FIXED CODE ###

s = input()
S = [int(s[i]) for i in range(len(s))]
# print(S)
count = 0
before = 0
while 1:
    #print("S:", S)
    is_continue = False
    # print(len(S))
    #deleted = False
    for i in range(max([before, 0]), len(S) - 1):
        #print(before, i)
        #print(S[i], S[i + 1])
        # print(S)
        if S[i] != S[i + 1]:
            # print(count)
            del S[i]
            del S[i]
            count += 2
            is_continue = True
            before = i - 2
            #deleted = True
            break
    if not is_continue:
        break
print(count)
### BUGGY CODE ###

N, K = map(int,input().split())
nums = list(map(int,input().split()))
ans = []

for i in range(N):
  ans.append((nums[i]+1)/2)

sums = []
for i in range(N-K+1):
  number =0
  for j in range(i,K+i):
    number += ans[j]
  sums.append(number)
print(max(sums))
  

### FIXED CODE ###

N, K = map(int,input().split())
nums = list(map(int,input().split()))
ans = []

for i in range(N):
  ans.append((nums[i]+1)/2)

M = sum(ans[0:K])
S = M
for i in range(K,N):
  S = S + ans[i] - ans[i-K]
  M = max(M,S)

print(M)
### BUGGY CODE ###

n = int(input())
s = list(range(n))
ans = 0
for i in range(n):
  s[i] = list(str(input()))
  s[i].sort()
  ans += s.count(s[i])-1
     
print(ans)

### FIXED CODE ###

n = int(input())
s = []
cnt = {}
ans = 0
for i in range(n):
  s_ = list(str(input()))
  s_.sort()
  s_ = "".join(s_)
  if s_ in cnt:
    ans += cnt[s_]
    cnt[s_] += 1
  else:
    cnt[s_] = 1

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

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

def main():
    n = int(input())
    a_list = list(map(int, input().split()))

    a_set = set(a_list)
    min_cnt = 0
    for i in a_set:
        cnt = a_list.count(i)
        if cnt - i >= 0:
            min_cnt += cnt - i
        else:
            min_cnt += cnt

    print(min_cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-
from collections import Counter

def main():
    n = int(input())
    a_list = list(map(int, input().split()))

    a_set = set(a_list)
    cnt = Counter(a_list)

    min_cnt = 0
    for i in a_set:
        if cnt[i] - i >= 0:
            min_cnt += cnt[i] - i
        else:
            min_cnt += cnt[i]

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

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [[-1]*(W+1) for _ in range(N-1)] #0~N-2
#DP[depth:0~N-1][0~W] calc()の結果をメモる
#DP[N-1][]については、W-pwsum>=N-1の重さならN-1の重さ
##W-pwsum<N-1の重さ なら 0
##→W-(N-1)>=pwsumとW-(N-1)<pwsumで場合分け
DP.append([0]*(W+1))
tmppwsum = 0
weiofMinus1, valofNminus1 = wv[N-1]
while W-weiofMinus1>=tmppwsum:
  DP[N-1][tmppwsum] = valofNminus1
  tmppwsum += 1


#合計pwsumの重さを入れた状態で、
#depth以降の品物を選ぶ場合の最大価値を返す関数
def calc(depth, pwsum):
  #メモ済みだったらメモした値を返す
  dp =  DP[depth][pwsum]
  if dp != -1: return dp
  
  nowWei, nowVal = wv[depth] #今選んでる品物のこと
  if pwsum + nowWei > W:
    #入れると重さ超過なので、入れずに次を考える
#    if depth >= N-1:
#      #今の品物が最後なら、以降得られる価値は0
#      DP[depth][pwsum] = 0
#      return 0
#    else:
    #次の品物が無い場合はDPで省かれている
      #次の品物がある場合、今のを入れずに次へいく
    irenai = calc(depth+1, pwsum)
    DP[depth][pwsum] = irenai
    return irenai
  if pwsum + nowWei <= W:
    #入れても大丈夫な場合
#    if depth >= N-1:
#      #今の品物が最後なら、今の品物しか入れられない
#      DP[depth][pwsum] = nowVal
#      return nowVal
    #次の品物が無い場合はDPで省かれている
      #次の品物がある場合、今のを入れる入れないの2択
    ireru = nowVal + calc(depth+1, pwsum+nowWei)
    irenai = calc(depth+1, pwsum)
    DP[depth][pwsum] = max(ireru, irenai)
    return max(ireru, irenai)
    
print(calc(0, 0))

### FIXED CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [0]*(W+1) #0~W
#各iにつき、残り重さがWの時の最大価値をDPに入れる


#i=N-1までいった時のmax(DP)が答え
for i in range(0, N, 1): #0~N-1
  w, v = wv[i]
  #残りwei(W-DPの2個目の添字)がw未満の場合入れられない
  #入れない場合は変えなければいい
  for nw in range(W, w-1, -1):
    iretaV = DP[nw-w] + v
    if iretaV > DP[nw]:
      DP[nw] = iretaV

print(max(DP))
### BUGGY CODE ###

from collections import deque
import sys 
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
not_root = set()
for i in range(m):
    x, y = map(int, input().split())
    not_root.add(y)
    adjacent_list[x].append(y)
root_cand = set(list(range(1, n+1))) - not_root
root_cand = deque(root_cand)
dp = [0] * (n+1)
def dfs(node, count):
    dp[node] = count + 1
    if len(adjacent_list[node]) != 0:
        for i in adjacent_list[node]:
            if dp[i] <= dp[node]:
                dfs(i, dp[node])
n = len(root_cand)
while n != 0:
    root = root_cand.pop()
    n -= 1
    dfs(root, -1)
print(max(dp))


### FIXED CODE ###

from collections import deque
import sys 
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
not_root = set()
for i in range(m):
    x, y = map(int, input().split())
    not_root.add(y)
    adjacent_list[x].append(y)
dp = [-1 for i in range(n+1)]
def cul(x):
    if dp[x] != -1:
        return dp[x]
    else:
        if len(adjacent_list[x]) == 0:
            return 0
        dp[x] = max([cul(i) + 1 for i in adjacent_list[x]])
        return dp[x]
for i in range(1,n+1):
    cul(i)
print(max(dp))
### BUGGY CODE ###

import numpy as np

R, C, K = map(int,input().split())
MAP = np.zeros((R, C), dtype=np.int64)
DP = np.zeros((R+1, C+1, 4), dtype=np.int64)

for _ in range(K):
    r, c, v = map(int,input().split())
    MAP[r-1][c-1] = v

for i in range(R):
    for j in range(C):
        tmp = DP[i][j+1][3]
        DP[i+1][j+1] = DP[i+1][j]
        DP[i+1][j+1][DP[i+1][j+1] < tmp] = tmp
        v = MAP[i][j]
        if v == 0:
            continue
        for k in range(2,-1,-1):
            DP[i+1][j+1][k+1] = max(DP[i+1][j+1][k + 1], DP[i+1][j+1][k] + v)

print(max(DP[R][C]))

### FIXED CODE ###

R, C, K = map(int,input().split())
MAP = [[0 for i in range(C)] for j in range(R)]
DP = [[[0 for i in range(C+1)] for j in range(4)] for k in range(R+1)]
 
for _ in range(K):
    r, c, v = map(int,input().split())
    MAP[r-1][c-1] = v
 
for i in range(R):
    for j in range(4):
        for k in range(C):
            DP[i+1][j][k+1] = max(DP[i][3][k+1], DP[i+1][j][k])
            if j == 0:
                continue
            v = MAP[i][k]
            if v == 0:
                continue
            DP[i+1][j][k+1] = max(DP[i+1][j][k+1], max(DP[i][3][k+1], DP[i+1][j-1][k]) + v)

print(DP[R][3][C])
### BUGGY CODE ###

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


m = 0

for i in range(n-1):
    s = xor = a[i]
    for j in range(i+1, n):
        xor = xor ^ a[j]
        s += a[j]
        if xor == s:
            m += 1

print(m+n)

### FIXED CODE ###

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

cur = a[0]
ans = 0
rp = 1

for lp in range(n):
    while rp < n and cur & a[rp] == 0:
        cur += a[rp]
        rp += 1
    ans += rp - lp
    cur -= a[lp]

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

N, M = map(int, input().split())
A = set(map(int, input().split()))
num = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
ans = {0: 0, 1: 0}
for i in range(2, N + 1):
    x = 0
    for j in range(1, 10):
        k = num[j]
        if j not in A or i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        if i - k in ans:
            an = ans[i - k]
            if an == 0:
                continue
            x = max(x, an * 10 + j)
            x = max(x, j * 10 ** len(str(an)) + an)
    ans[i] = x
print(ans[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = {}
for i in range(N + 1):
    x = 0
    for j in A:
        k = num[j - 1]
        if i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        an = ans[i - k]
        if an == 0:
            continue
        x = max(x, an * 10 + j)
    ans[i] = x
print(ans[N])
### BUGGY CODE ###

s = input()
q = int(input())
for _ in range(q):
    a = list(input().split())
    if a[0]=="1":
        s=s[::-1]
    else:
        if a[1]=='1':
            s=a[2]+s
        else:
            s=s+a[2]

print(s)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
que = deque([s])
flg=False
for _ in range(q):
    a = list(input().split())
    if a[0]=='1':
        flg=not(flg)
#        s=s[::-1]
    else:
        if flg and a[1]=='1' or not flg and a[1]=='2':
            que.append(a[2])
        else:
            que.appendleft(a[2])

ans = ''.join(que)

if flg:
    ans = ans[::-1]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from itertools import product
INF = 10**18

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: max(abs(xyp[0]), abs(xyp[1])) * xyp[2], reverse=True)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    print(*ans, sep='\n')

sol()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

n = int(input())
s=input()
ans=0

import itertools
for seq in itertools.combinations(range(n),3):
    if s[seq[0]]!=s[seq[1]] and s[seq[1]]!=s[seq[2]] and s[seq[2]]!=s[seq[0]] and seq[1]-seq[0]!=seq[2]-seq[1]:
        ans+=1

print(ans)    

### FIXED CODE ###

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

ans=s.count("R")*s.count("G")*s.count("B")

for start in range(n):
    for kousa in range(n):
        if start+2*kousa>n-1:
            break
        if s[start]!=s[start+kousa] and s[start+kousa]!=s[start+2*kousa] and s[start+2*kousa]!=s[start]:
            ans-=1

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

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

c=1

for i in range(n):
    c*=a[i]

if c>10**18:
    print('-1')
else:
    print(c)

### FIXED CODE ###

import sys
n=int(input())
a=list(map(int,input().split()))

if 0 in a:
    print('0')
    sys.exit()

c=1

for i in range(n):
    c*=a[i]
    if c>10**18:
        print('-1')
        sys.exit()
    else:
        continue

print(c)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
numlist = []
for i in range(N-1):
    if S[i:i+2] == 'AC':
        numlist.append(i)

l = [0 for i in range(Q)]
r = [0 for i in range(Q)]
for i in range(Q):
    ll, rr = map(int, input().split())
    l[i], r[i] = ll-1, rr-1

for i in range(Q):
    now = [n for n in numlist if n>= l[i] and n <= r[i]-1]
    print(len(now))


### FIXED CODE ###

import bisect
N, Q = map(int, input().split())
S = input()
numlist = []
for i in range(N-1):
    if S[i:i+2] == 'AC':
        numlist.append(i)

l = [0 for i in range(Q)]
r = [0 for i in range(Q)]
for i in range(Q):
    ll, rr = map(int, input().split())
    l[i], r[i] = ll-1, rr-1

for i in range(Q):
    hajime = bisect.bisect_left(numlist, l[i])
    owari = bisect.bisect_right(numlist,r[i]-1)
    print(owari - hajime)
### BUGGY CODE ###

# 埋める配列
# dp[x] = 足場0からスタートして足場xに着地するときに足場xまでに払うコストの最小値

# 計算方法
# dp[0] = 0
# dp[x] = min(dp[x - 1] + |h[x] - h[x - 1]|, dp[x - 2] + |h[x] - h[x - 2]|, ... ,  dp[x - K] + |h[x] - h[x - K]|)

# 埋める順番
# xが小さい順

N, K = map(int, input().split())
H = list(map(int, input().split()))
INF = 10 ** 18

dp = [0] * (N + 5)

for i in range(1, N):
    dp[i] = INF
    for j in range(1, K + 1):
        if i - j >= 0: # 脳死
            dp[i] = min(dp[i], dp[i - j] + abs(H[i] - H[i - j]))

print(dp[N - 1])

### FIXED CODE ###

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

# 0-indexed
INF = 10 ** 15
dp = [INF] * N
dp[0] = 0

for i in range(N):
  for k in range(1, K+1):
    if i + k < N and dp[i] + abs(H[i+k] - H[i]) < dp[i+k]:
      dp[i+k] = dp[i] + abs(H[i+k] - H[i])
      
print(dp[-1])
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
A = LI()
ans = A[0]
for i in range(1, N):
    ans = ans*A[i]
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
A = LI()
ans = A[0]
if 0 in A:
    ans = 0
else:
    for i in range(1, N):
        if ans > 10**18:
            ans = -1
            break
        else:
            ans = ans*A[i]
if ans > 10**18:
    ans = -1
print(ans)
### BUGGY CODE ###

s=input()
dp=[[0]*4 for i in range(len(s)+1)]
dp[0][0]=1
mod=10**9+7
from copy import deepcopy
def dp_next(dp,i,j,mod):
    dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j])%mod
for i in range(len(s)):
    if s[i]=='?':
        for j in range(4):
            dp[i+1][j]=dp[i][j]*3
        for j in range(3):
            dp_next(dp,i,j,mod)
        continue
    dp[i+1]=deepcopy(dp[i])
    if s[i]=='A':
        dp_next(dp,i,0,mod)
    elif s[i]=='B':
        dp_next(dp,i,1,mod)
    elif s[i]=='C':
        dp_next(dp,i,2,mod)
print(dp[-1][3])

### FIXED CODE ###

s=input()
import numpy as np
dp=np.zeros((len(s)+1,4),dtype=np.int64)
dp[0][0]=1
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        dp[i+1]=dp[i]*3
        dp[i+1][1:]+=dp[i][:3]
        dp[i+1]%=mod
    else:
        dp[i+1]=dp[i]
        j=ord(s[i])-ord('A')
        dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j])%mod
print(dp[-1][3])
### BUGGY CODE ###

import math
s = input()
n=int(s)
ans=0
for i in range(1,n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            ans+=math.gcd(math.gcd(i,j),k)
print(ans)


### FIXED CODE ###

import math
s = input()
k = int(s)
n = 3
ans={}
for i in reversed(range(1, k+1)):
    ans[i]=math.floor(k/i)**n
    l=2
    j=i*l
    while j<=k:
        ans[i]=ans[i]-ans[j]
        l +=1
        j = i*l
res=0
for i in ans:
    res+=i*ans[i]
print(res)
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
k=0
for i in range(a,b+1):
    if i%c!=0 and i%d!=0:k+=1
print(k)

### FIXED CODE ###

import fractions
a,b,c,d=map(int,input().split())
cdgcd=(c*d)//fractions.gcd(c,d)
print(b-(a-1)-(b//c) +((a-1)//c) -(b//d) +((a-1)//d) +(b//cdgcd) -(a-1)//cdgcd)