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

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

mod = 10**9 +7
n, k = map(int, input().split())
a = list(map(int, input().split()))
ascA = sorted(a)

sum_ = 0
for i in range(n-k+1):
    for j in range(i+k-1, n):
        f = ascA[j]-ascA[i]
        c = cmb(j-i-1, k-2, mod)
        #print("%d %d"%(f,c))
        sum_ = (sum_ + (f*c) % mod) % mod

print(sum_)

### FIXED CODE ###

def cmb(n,k, MOD):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
ascA = sorted(a)

MAX_N = n
fac  = [0 for _ in range(MAX_N)]
finv = [0 for _ in range(MAX_N)]
inv  = [0 for _ in range(MAX_N)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_N):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

sum_ = 0
for i in range(n-k+1):
    f = ascA[n-i-1] - ascA[i]
    c = cmb(n-i-1, k-1, MOD)
    sum_ = (sum_ + (f*c)%MOD) % MOD
    '''
    for j in range(i+k-1, n):
        f = ascA[j]-ascA[i]
        c = cmb(j-i-1, k-2, MOD)
        #print("%d %d"%(f,c))
        sum_ = (sum_ + (f*c) % MOD) % MOD
    '''

print(sum_)
### BUGGY CODE ###

import statistics
import copy

N = int(input())
X = list(map(int,input().split(" ")))
for i in range(N):
    Y = copy.deepcopy(X)
    Y[i] = 0
    Y.remove(0)
    print(statistics.median(Y))


### FIXED CODE ###

import copy
N = int(input())
X = list(map(int,input().split(" ")))
Y = copy.deepcopy(X)
Y.sort()
B = (Y[N//2]+Y[N//2-1])/2

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

import sys
def isPrimeNumber(candidate):
    divisor = 2
    while divisor < candidate:
        if candidate % divisor == 0:
            return False
        else:
            divisor += 1
    return True

for line in sys.stdin:
    primeNumberCount = 0
    n = int(line.rstrip('\n'))
    candidate = 2
    while candidate <= n:
        if isPrimeNumber(candidate):
            primeNumberCount += 1
        candidate += 1
    print primeNumberCount

### FIXED CODE ###

import math
import sys

n = 999999
nums = [1] * (n+1)
nums[:2] = [0,0]
    
cnt = 0
while cnt <= math.sqrt(n):
    flg = nums[cnt]
    if flg == 1:
        k = 2
        while k*cnt <= n:
            nums[k*cnt] = 0
            k += 1
    cnt += 1


for line in sys.stdin:
    n = int(line)
    print sum(nums[:n+1])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
M=1
for i in range(N):
    M*=A[i]
if M <= 10**18:
    print(int(M))
else:
    print('-1')

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
M=1
if 0 in A:
    print('0')
else:
    for i in range(len(A)):
        M*=A[i]
        if M > 10**18:
            break
    if M > 10**18:
        print('-1')
    else:
        print(int(M))
### BUGGY CODE ###

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

for i in range(N):
  a.append(a[i]+1)
  a.append(a[i]-1)

ans=0

for i in range(min(a), max(a)+1):
  ans = max(ans, a.count(i))

print(ans)

### FIXED CODE ###

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

d = [0]*(10**5+1)
for i in range(N):
  d[a[i]]+=1

ans=0
for i in range(10**5):
  ans = max(ans, d[i-1]+d[i]+d[i+1])

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

import sys
input = sys.stdin.readline
from collections import defaultdict
d = defaultdict(list)

sh,sw,m = map(int,input().split())
H = [0]*sh
W = [0]*sw
for i in range(m):
    h,w = map(int,input().split())
    d[h-1].append(w-1)
    H[h-1] += 1
    W[w-1] += 1

maxh = max(H)
maxw = max(W)
# print(H,W)
# print(maxh,maxw)

hlist = []
wlist = []

for i in range(sh):
    if H[i] == maxh:
        hlist.append(i)
for j in range(sw):
    if W[j] == maxw:
        wlist.append(j)
# print(hlist,wlist)

maxi = maxh+maxw-1
for i in hlist:
    for j in wlist:
        if j not in d[i]:
            maxi += 1
            print(maxi)
            exit()
print(maxi)

### FIXED CODE ###

import sys
input = sys.stdin.readline
l = set()

sh,sw,m = map(int,input().split())
H = [0]*sh
W = [0]*sw
for i in range(m):
    h,w = map(int,input().split())
    l.add((h-1,w-1))
    H[h-1] += 1
    W[w-1] += 1

maxh = max(H)
maxw = max(W)
# print(H,W)
# print(maxh,maxw)

hlist = []
wlist = []

for i in range(sh):
    if H[i] == maxh:
        hlist.append(i)
for j in range(sw):
    if W[j] == maxw:
        wlist.append(j)
# print(hlist,wlist)

if len(hlist)*len(wlist) > m:
    print(maxh+maxw)
    exit()

ans = maxh+maxw-1
for i in hlist:
    for j in wlist:
        if (i,j) not in l:
            print(ans+1)
            exit()
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split(" "))
arr = list(map(int, input().split(" ")))
new_arr = set(arr)

ans_date = []
for i in new_arr:
  date = []
  num_count = arr.count(i)
  num = i
  date.append(num_count)
  date.append(num)
  ans_date.append(date)
ans_date.sort()

t = len(ans_date)
x = t - k
if x <= 0:
  print(0)
  exit()
ans = 0
for l in range(x):
  ans += ans_date[l][0]
print(ans)

### FIXED CODE ###

from collections import Counter

n, k = map(int, input().split(" "))
As = list(map(int, input().split(" ")))

c = Counter(As)
# print(c)
common = c.most_common(k)
# print(common)

common_sum = sum([item[1] for item in common])
print(n - common_sum)
### BUGGY CODE ###

from queue import deque
from copy import deepcopy

    
H, W = map(int, input().split())
S = []
cnt = []
Checked = [[0 for _ in range(W)] for _ in range(H)]


for _ in range(H):
    S.append([i for i in input()])
    
for start_h in range(H):
    for start_w in range(W):
        if S[start_h][start_w] == '#':
            continue
        for goal_h in range(H):
            for goal_w in range(W):
                if S[goal_h][goal_w] == '#':
                    continue
                if start_h == goal_h or start_w == goal_w:
                    cnt.append(abs(start_h - goal_h) + abs(start_w - goal_w))
                    continue
                    
                q = deque([[start_h, start_w]])
                checked = deepcopy(Checked)
                c = 0
                tmp = []
                while q:
                    h, w = q.popleft()
                    if checked[h][w]:
                        continue
                    checked[h][w] = 1
                    if h == goal_h and w == goal_w:
                        cnt.append(c)
                        break
                        
                    for dw, dh in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                        next_h, next_w = h + dh, w + dw
                        if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                            continue
                        if S[next_h][next_w] == '#':
                            continue
                        if [next_h, next_w] in tmp or checked[next_h][next_w]:
                            continue
                        tmp.append([next_h, next_w])
                    if not q:
                        q.extend(tmp)
                        tmp = []
                        c += 1

print(max(cnt))

### FIXED CODE ###

from queue import deque
from copy import deepcopy

    
H, W = map(int, input().split())
S = [['#'] * (W + 2)]
cnt = []
Checked = [[0 for _ in range(W+2)] for _ in range(H+2)]


for _ in range(H):
    S.append(['#'] + [i for i in input()] + ['#'])
S.append(['#']*(W + 2))

for start_h in range(1, H+1):
    for start_w in range(1, W+1):
        if S[start_h][start_w] == '#':
            continue
        q = deque([[start_h, start_w]])
        checked = deepcopy(Checked)
        c = 0
        tmp = []
        while q:
            h, w = q.popleft()
            if checked[h][w]:
                 continue
            checked[h][w] = 1
                    
            for dw, dh in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                next_h, next_w = h + dh, w + dw
                if S[next_h][next_w] == '#':
                    continue
                if [next_h, next_w] in tmp or checked[next_h][next_w]:
                    continue
                tmp.append([next_h, next_w])
            if not q:
                q.extend(tmp)
                tmp = []
                c += 1
        cnt.append(c-1)
            
print(max(cnt))
### BUGGY CODE ###

A, B, C = map(int, input().split())
ans = "NO"
for i in range(A, 100000000, A): 
        if i % B == C:
                ans = "YES"
                break
print(ans)

### FIXED CODE ###

A, B, C = map(int, input().split())
ans = "NO"
for i in range(A, 100000000, A): 
        if i % B == C:
                ans = "YES"
                break
print(ans)
### BUGGY CODE ###

def calc():
 N,M = map(int,input().split())
 gcd = M // N
 while gcd > 0:
  tmp = M - gcd
  if tmp % gcd == 0:
   break
  gcd = gcd - 1
 return(gcd)
print(calc())

### FIXED CODE ###

def calc():
 N,M = map(int,input().split())
 for gcd in range(M // N,0,-1):
  if M % gcd == 0:
   break
 return(gcd)
print(calc())
### BUGGY CODE ###

import itertools
import numpy as np
import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)

N = int(input())
S = list(input())  # len:N

S = sorted(S)  #  アルファベット順に並べ替え
U = [0] * 26  #  ユニーク数数え上げ
tmp = "0"
count = 0
u_count = 0
for i in range(N):
    if i > 0:
        if tmp == S[i]:
            U[count] += 1
        else:
            tmp = S[i]
            count += 1
            U[count] += 1
    else:
        tmp = S[i]
        U[count] += 1


for u in range(26):
    if U[u] != 0:
        u_count += 1

U = sorted(U)

for i in range(len(U)):
    if U[0] == 0:
        U.pop(0)

count = 0

for i in range(1, u_count+1):
    count += np.sum(np.array(list(itertools.combinations(U, i))).prod(axis=1))

a = 10 ** 9 + 7
print(count % a)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = input()
answer = 1
counter = Counter(S).most_common()

for i in range(len(counter)):
    answer = answer * (counter[i][1] + 1) % (10**9 + 7)

print(answer-1)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N // G) + 1):
        V = N - (r * R + g * G)
        if V >= 0 and V % B == 0:
            cnt += 1
print(cnt)


### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N - (r * R)) // G + 1):
        V = N - (r * R + g * G)
        if V >= 0 and V % B == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, C = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(C)]
L = sorted(L, key=lambda x: (x[1], -x[2], x[0]), reverse=True)
dist = [float('inf')]*(N+1)
dist[-1] = 0
for l, r, c in L:
    for d in range(l, r):
        dist[d] = min(dist[r]+c, dist[d])
if dist[1] == float('inf'):
    print(-1)
else:
    print(dist[1])


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


N, C = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(C)]
L = sorted(L, key=lambda x: (x[1], -x[2], x[0]), reverse=True)

Seg = SegmentTree(N+1, func=lambda a, b: min(a, b))
Seg.set(N, 0)
Seg.build()

dist = [float("inf")]*(N+1)
dist[-1] = 0
for l, r, c in L:
    new = min(Seg.query(l, r+1)+c, Seg.query(l, l+1))
    Seg.update(l, new)
ans = Seg.query(1, 2)
if ans == float('inf'):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
import bisect
import heapq
from collections import deque


def main():
  ## input
  N,Q = map(int, input().split())
  STX = [[0,0,0] for i in range(N)]
  for i in range(N):
    s,t,x = map(int, input().split())
    STX[i] = [s-x, t-x-1, x]
  STX = sorted(STX, key=lambda x:x[2])
  Dn = [int(input()) for _ in range(Q)]+[10**10]

  ans = []
  for s,t,x in STX:
    l = bisect.bisect_left(Dn,s)
    r = bisect.bisect_right(Dn,t)-1
    while Dn[l] <= t:
      heapq.heappush(ans,(Dn[l],x))
      Dn.pop(l)
  for d in Dn:
    heapq.heappush(ans,(d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans)>1:
    print(heapq.heappop(ans)[1])


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])

def maxvalue_recursive(N, W):
    def memoize(func):
        func.d = d = {}
        def _f(*va):
            if va not in d: d[va] = func(*va)
            return d[va]
        return _f

    @memoize
    def maxvalue(i, w):
        if i < 0: return 0
        if w < ws[i]:
            return maxvalue(i - 1, w)
        else:
            return max(maxvalue(i - 1, w), maxvalue(i - 1, w - ws[i]) + vs[i])

    res = maxvalue(N - 1, W)
    return res

def maxvalue_dp(N, W):
    dp = [0] * (W + 1)
    for i in range(N):
        dp = [max(dp[w], dp[w - ws[i]] + vs[i] if w >= ws[i] else 0) for w in range(W + 1)]
    return dp[-1]

#print(maxvalue_recursive(N, W))
print(maxvalue_dp(N, W))

#import timeit
#print(timeit.timeit('maxvalue_recursive(N, W)', globals=globals(), number=10000))
#print(timeit.timeit('maxvalue_dp(N, W)', globals=globals(), number=10000))

### FIXED CODE ###

N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])

def maxvalue_recursive(N, W):
    def memoize(func):
        func.d = d = {}
        def _f(*va):
            if va not in d: d[va] = func(*va)
            return d[va]
        return _f

    @memoize
    def maxvalue(i, w):
        if i < 0: return 0
        if w < ws[i]:
            return maxvalue(i - 1, w)
        else:
            return max(maxvalue(i - 1, w), maxvalue(i - 1, w - ws[i]) + vs[i])

    res = maxvalue(N - 1, W)
    return res

def maxvalue_dp(N, W, ws, vs):
    import numpy as np
    dp = np.zeros(W + 1, 'int64')
    ws = np.array(ws, 'int64')
    vs = np.array(vs, 'int64')
    for i in range(N):
        idx = np.arange(W + 1) - ws[i]
        dp = np.maximum(dp, (dp[idx] + vs[i]) * (idx >= 0))
    return dp[-1]

#print(maxvalue_recursive(N, W))
print(maxvalue_dp(N, W, ws, vs))

#import timeit
#print(timeit.timeit('maxvalue_recursive(N, W)', globals=globals(), number=10000))
#print(timeit.timeit('maxvalue_dp(N, W)', globals=globals(), number=10000))
### BUGGY CODE ###

nm = [int(i) for i in input().split()]
lr = [[int(i) for i in input().split()] for i in range(nm[1])]

a = [{j for j in range(lr[i][0], lr[i][1]+1)} for i in range(nm[1])]
b = set()
for i in range(len(a)):
    if b == set():
        b = a[i]
    b = b & a[i]
print(len(b))

### FIXED CODE ###

nm = [int(i) for i in input().split()]
lr = [[int(i) for i in input().split()] for i in range(nm[1])]

l = [i[0] for i in lr]
r = [i[1] for i in lr]
print(len(range(max(l), min(r)+1)))
### BUGGY CODE ###

import sys
k = int(input())
if k % 2 == 0 or k % 5 == 0:
  print('-1')
  sys.exit()
s = 7
c = 1
while True:
  if s % k == 0:
    break
  s = 10 * s + 7
  c += 1
print(c)

### FIXED CODE ###

import sys
k = int(input())
if k % 2 == 0 or k % 5 == 0:
  print('-1')
  sys.exit()
s = 7
c = 1
while True:
  if s % k == 0:
    break
  s = (10 * s + 7) % k
  c += 1
print(c)
### BUGGY CODE ###

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(1, N+1):
    weight = WV[i-1][0]
    value = WV[i-1][1]
    for w in range(W+1):
        if w-weight<0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w-weight]+value, dp[i-1][w])

print(dp[N][W])


### FIXED CODE ###

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(1, N+1):
    weight = WV[i-1][0]
    value = WV[i-1][1]
    for w in range(W+1):
        if w-weight<0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w-weight]+value, dp[i-1][w])
print(dp[N][W])
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    mod = 998244353
    
    a, b, c, d = map(int, input().split())
    dp = dict()
    for i in range(a, c+1):
        for j in range(b, d+1):
            if i == a and j == b:
                dp[(i, j)] = 1
                continue
            if j == b:
                dp[(i, j)] = dp[(i-1, j)]*j%mod
                continue
            if i == a:
                dp[(i, j)] = dp[(i, j-1)]*i%mod
                continue
            dp[(i, j)] = (dp[(i-1, j)]*j+dp[(i, j-1)]*i+mod-dp[(i-1, j-1)]*(i-1)*(j-1))%mod
    print(dp[(c, d)])        
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    mod = 998244353
    
    a, b, c, d = map(int, input().split())
    dp = [[0]*(d+1) for _ in range(c+1)]
    for i in range(a, c+1):
        for j in range(b, d+1):
            if i == a and j == b:
                dp[i][j] = 1
                continue
            if j == b:
                dp[i][j] = dp[i-1][j]*j%mod
                continue
            if i == a:
                dp[i][j] = dp[i][j-1]*i%mod
                continue
            dp[i][j] = (dp[i-1][j]*j+dp[i][j-1]*i+mod-dp[i-1][j-1]*(i-1)*(j-1)%mod)%mod
    print(dp[c][d])        
            

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

k, s = map(lambda x: int(x), input().split(' '))

r = 0
for a in range(k + 1):
    for b in range(k + 1):
        for c in range(k + 1):
            if a + b + c == s:
                r += 1

print(r)


### FIXED CODE ###

k, s = map(lambda x: int(x), input().split(' '))
r = 0
for a in range(k + 1):
    if a > s:
        break
    for b in range(k + 1):
        if a + b > s:
            break
        elif s - (a + b) < k + 1:
            r += 1
print(r)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
px = [ list(map(int,input().split())) for _ in range(q) ]
# print(tree)
# print(px)
c = [0]*n
for i in range(len(px)):
    c[px[i][0]-1] += px[i][1]
# print(c)
# for i in range(1,n):
#     c[i] += c[min(tree[i])-1]
visited = [0]*n
visited[0] = 1
while sum(visited)!=n:
    for i in range(1,n):
        for j in range(len(tree[i])):
            node_tmp = tree[i][j]
            if visited[node_tmp-1]==1 and visited[i]==0:
                c[i] += c[node_tmp-1]
                visited[i] = 1
            else:
                pass
print(" ".join(map(str,c)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
# px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
# for i in range(len(px)):
for _ in range(q):
    p,x = map(int,input().split())
    c[p-1] += x  
visited = [0]*n
cnd = [1]   # current_node
while len(cnd)>0:
    nnd = []
    for j in cnd:
        visited[j-1]=1
        ko = tree[j-1]
        for k in ko:
            if visited[k-1]==0:
                c[k-1] += c[j-1]
                nnd.append(k)
    cnd = nnd
print(" ".join(map(str,c)))
### BUGGY CODE ###

import numpy as np

N,K = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.full(N,10**10)
dp[0] = 0
for i in range(1,N):
    start = max(0,i-K)
    dp[i] = min(dp[start:i]+np.abs(h[i]-h[start:i]))
print(int(dp[-1]))

### FIXED CODE ###

import numpy as np

N,K = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.full(N,10**10)
dp[0] = 0
for i in range(1,N):
    start = max(0,i-K)
    dp[i] = np.min(dp[start:i]+np.abs(h[i]-h[start:i]))
print(int(dp[-1]))
### BUGGY CODE ###

L, A, B, M = [int(s) for s in input().split()]

s = ''

for i in range(L):
    s += str(A+B*i)
    
print(int(s) % M)

### FIXED CODE ###

import numpy as np

L, A, B, M = map(int, input().split())

def dot(A, B, mod):
    r = len(A)
    c = len(B[0])
    m = len(A[0])
    res = [[0] * c for _ in range(r)]
    
    for i in range(r):
        for j in range(c):
            for k in range(m):
                res[i][j] += A[i][k] * B[k][j] % mod
                res[i][j] %= mod
    
    return res

def rec_pow(k, n, mod):
    if n == 1:
        return k
    
    k2 = dot(k, k, mod)
    if n % 2 ==0:
        return rec_pow(k2, n//2, mod)
    else:
        return dot(rec_pow(k2, n//2, mod), k, mod)

s = [[0, A%M, 1]]

for d in range(1, 19):
    n1 = min(max(0, (10**d-1-A)//B+1), L)
    n0 = min(max(0, (10**(d-1)-1-A)//B+1), L)
    n = n1 - n0
    if n == 0:
        continue
        
    k = [[pow(10, d, M), 0, 0], [1, 1, 0], [0, B%M, 1]]
    
    s = dot(s, rec_pow(k, n, M), M)
    
    if n1 >= L:
        break
        
print(s[0][0])
### BUGGY CODE ###

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

dp = [[] for _ in range(n)]
dp[0] = 0

for i in range(1,n):
    tmp = float('inf')
    for j in range(1,k+1):
        if i-j < 0:
            continue
        tmp = min(dp[i-j] + abs(hl[i]-hl[i-j]),tmp)
    dp[i] = tmp
print(dp[-1])



### FIXED CODE ###

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

dp = [[] for _ in range(n)]
dp[0] = 0

for i in range(1,n):
    tmp = float('inf')
    for j in range(1,k+1):
        if i-j < 0:
            continue
        tmp = min(dp[i-j] + abs(hl[i]-hl[i-j]),tmp)
    dp[i] = tmp
print(dp[-1])