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

import sys
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    def print(self):
        for order in ['Inorder', 'Preorder']:
            print('', *[node.key for node in self.root.walk(order)])
    
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def walk(self, order):
        orders = {'Preorder':[self, self.left, self.right], 'Inorder':[self.left, self, self.right], 'Postorder':[self.left, self.right, self]}
        
        for node in orders[order]:
            if node == self:
                yield node
            elif node:
                for childnode in node.walk(order):
                    yield childnode

                    
                    
tree = Tree()
func = {'insert':tree.insert, 'print':tree.print}

n = int(sys.stdin.readline())
for _ in range(n):
    command = sys.stdin.readline().split()
    func[command[0]](*map(int, command[1:]))

### FIXED CODE ###

import sys
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    def print(self):
        print('',' '.join(map(str, self.root.inwalk())))
        print('',' '.join(map(str, self.root.prewalk())))
    
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret
    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret
tree = Tree()
n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    else:
        tree.print()
### BUGGY CODE ###

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

N = int(input().strip())
#-----

def get_divisor(n :int) -> dict:
    ans = []

    for i in range(1, int(n**(1/2)+1) ):
        if  n % i == 0:
            ans.append(i)
            
            d = n / i
            if (d != i) and (d % 1 == 0):
                ans.append( int(d) )
    
    return ans



sum_f = 0

for i in range(1,N+1):
    num_div = len( get_divisor(i) )
    sum_f += i * num_div

print(sum_f)


### FIXED CODE ###

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

N = int(input().strip())
#-----

ans = 0

for k in range(1, N+1):
    quot = N // k  # quotient
    num_divisor = quot * (quot + 1) // 2
    
    ans += k * num_divisor


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

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


dict_A={}
B=list(set(A))
sum=0


for b in B:
    a=A.count(b)
    dict_A[b]=a-1
    sum+=a*(a-1)//2

for a in A:
    print(sum-dict_A[a])

        

### FIXED CODE ###

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


dict_A={}
B=list(set(A))
sum=0


for a in A:
    if a not in dict_A.keys():
        dict_A[a]=1
    else:
        dict_A[a]+=1
for b in B:
    sum+=dict_A[b]*(dict_A[b]-1)//2

for a in A:
    print(sum-dict_A[a]+1)
### BUGGY CODE ###

from collections import Counter
import math

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

dic = Counter(a)

ans = 0

memo = {}

for ai in a:
    cnt = 0
    f = 1
    if ai not in memo:
        for i in range(1, int(math.sqrt(ai))+1):
            if ai % i == 0:
                d = i
                if d in dic:
                    cnt += dic[d]
                if d == ai:
                    cnt -= 1
                if cnt > 0:
                    f = 0
                    break
                if i != ai // i:
                    d = ai // i
                    if d in dic:
                        cnt += dic[d]
                    if d == ai:
                        cnt -= 1
                    if cnt > 0:
                        f = 0
                        break
    else:
        f = memo[ai]
    ans += f
    memo[ai] = f

print(ans)
    

            




### FIXED CODE ###

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

a.sort()
am = a[-1]

memo = [0] * (am+1)

for ai in a:
    memo[ai] = 1

p = -1

for ai in a:
    if ai == p:
        memo[ai] = 0
        continue
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0
    p = ai

print(sum(memo))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):

    l = [0] * 2019
    ps = ""
    for i in range(1, len(S) + 1):
        ps = S[-i:]
        l[ int(ps) % 2019 ] += 1

    
    ans = 0
    for i in range(0, len(l)):
        ans += l[i] * (l[i] - 1) // 2
    
    ans += l[0]
    
    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):

    l = [0] * 2019
    ps = 0
    d = 1
    for i in range(1, len(S) + 1):
        ps += int(S[-i]) * d
        l[ ps % 2019 ] += 1
        d = d * 10 % 2019

    ans = 0
    for i in l:
        ans += i * (i - 1) // 2
    
    ans += l[0]
    
    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

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

def prm(a):
  if a == 1 or a == 4:
    return False
  for i in range(2,int((a)**0.5+1)):
    if a%i == 0:
      return False
  else:
    return True
prime = []
for i in range(1,10**6+1):
  if prm(i):
    prime.append(i)
def sepa(a):
  ans = []
  while a>1:
    for x in prime:
      if a%x == 0:
        ans.append(x)
        a = a//x
        break
    else:
      ans.append(a)
      a = 1
  return Counter(ans)
n,p = map(int,input().split())
c = sepa(p)
ans = 1
for k,v in c.values():
  if n<=v:
    ans *= k**(v//n)
print(ans)

### FIXED CODE ###

from collections import Counter
def prm(a):
  if a == 1 or a == 4:
    return False
  for i in range(2,int((a)**0.5+1)):
    if a%i == 0:
      return False
  else:
    return True
prime = []
for i in range(1,10**6+1):
  if prm(i):
    prime.append(i)
def sepa(a):
  ans = []
  while a>1:
    for x in prime:
      if a%x == 0:
        ans.append(x)
        a = a//x
        break
    else:
      ans.append(a)
      a = 1
  return Counter(ans)
n,p = map(int,input().split())
c = sepa(p)
ans = 1
for k,v in c.items():
  if n<=v:
    ans *= k**(v//n)
print(ans)
### BUGGY CODE ###

# ABC073C - Write and Erase
import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
    m = int(input())
    if m in arr:
        arr.pop(arr.index(m))
    else:
        arr.append(m)
print(len(arr))

### FIXED CODE ###

# ABC073C - Write and Erase
import sys
input = sys.stdin.readline

n = int(input())
arr = set()
for _ in range(n):
    m = int(input())
    if m in arr:
        arr.remove(m)
    else:
        arr.add(m)
print(len(arr))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
X=int(input())

if X==1:
    print(1)
    exit()
elif X==2:
    print(2)
    exit()

l=[1]
i=2
while True:
    temp=[]
    for item in l:
        temp.append(item+i)
    if X in temp:
        print(i)
        exit()
    else:
        l+=temp
        i+=1

### FIXED CODE ###

# coding: utf-8
# Your code here!
X=int(input())

i=0
count=0
while True:
    i+=1
    count+=i
    if count>=X:
        print(i)
        exit()
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]
    A = [ab for ab in AB if ab[0] == 1]
    B = [ab for ab in AB if ab[1] == N]

    result = 'IMPOSSIBLE'
    for a in A:
        for b in B:
            if a[1] == b[0]:
                result = 'POSSIBLE'
    print(result)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N, M = map(int, input().split())
    # AB = [list(map(int, input().split())) for _ in range(M)]
    from_1 = [False] * N
    to_N = [False] * N
    for _ in range(M):
        a, b = map(int, input().split())
        if a == 1:
            from_1[b - 1] = True
        elif b == N:
            to_N[a - 1] = True
    for i in range(1, N):
        if from_1[i] and to_N[i]:
            print('POSSIBLE')
            break
    else:
        print('IMPOSSIBLE')


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

import sys
from queue import Queue


def get_costs(S):
    costs = [[0 for w in range(len(S[0]))] for h in range(len(S))]
    for h in range(len(S)):
        for w in range(len(S[0])):
            if S[h][w] == '#':
                costs[h][w] = -1
    return costs


def print_costs(costs):
    for c in costs:
        print(c)


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_h in range(H):
        for start_w in range(W):
            costs = get_costs(S)
            queue = Queue()
            queue.put((start_h, start_w, 1))
            cost = 1
            while not queue.empty():
                (y, x, c) = queue.get()
                if not (0 <= y < len(costs) and 0 <= x < len(costs[0])):
                    continue
                if costs[y][x] != 0:
                    continue
                # print("({},{}): {}".format(y, x, c))
                costs[y][x] = c
                cost = c
                queue.put((y - 1, x, c + 1))
                queue.put((y, x + 1, c + 1))
                queue.put((y + 1, x, c + 1))
                queue.put((y, x - 1, c + 1))
            if cost > max_cost:
                max_cost = cost
            # print("--- cost={}".format(max_cost))
            # print_costs(costs)
            # print()

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from queue import Queue


def print_costs(costs):
    for c in costs:
        print(c)


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_y in range(H):
        for start_x in range(W):
            if S[start_y][start_x] == '#':
                continue
            costs = [[0 for w in range(W)] for h in range(H)]
            costs[start_y][start_x] = 1
            queue = Queue()
            queue.put((start_y, start_x))
            cost = 1
            while not queue.empty():
                (y, x) = queue.get()
                # print("({},{}): {}".format(y, x, c))
                for (next_y, next_x) in [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]:
                    if 0 <= next_y < H and 0 <= next_x < W and S[next_y][next_x] == '.' and costs[next_y][next_x] == 0:
                        costs[next_y][next_x] = costs[y][x] + 1
                        if cost < costs[next_y][next_x]:
                            cost = costs[next_y][next_x]
                        queue.put((next_y, next_x))
            if cost > max_cost:
                max_cost = cost
            # print("--- cost={}".format(max_cost))
            # print_costs(costs)
            # print()

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


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

s = str(input())
n = int(input())
 
for i in range(n):
    q = list(map(str,input().split()))
    if len(q) == 1 and q[0] == "1":
        s = s[::-1]
    elif q[1] == "1":
        s = q[2] + s
    elif q[1] == "2":
        s = s + q[2]
 
 
print(s)

### FIXED CODE ###

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

right = ""
left = ""

flag = 0
for i in range(n):
    q = list(map(str,input().split()))
    if len(q) == 1:
        flag = 1 - flag 
    elif q[1] == "1":
        if flag == 0:
            left = q[2] + left
        else:
            right = right + q[2]
    else:
        if flag == 0:
            right = right + q[2]
        else:
            left = q[2] + left


if flag == 0:
    print(left + s + right)
elif flag == 1:
    print(right[::-1] + s[::-1] + left[::-1])
### BUGGY CODE ###


import numpy as np

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

move_list = []
checker = np.zeros(N+1 ,dtype = int)
for LR in LRs:
    for i in range(LR[0], LR[1]+1):
        checker[i] = 1

for index, check in enumerate(checker):
    if(check == 1):
        move_list.append(index)

#print(move_list)

dp = np.zeros(N+1, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    for j in move_list:
        if(i < j):
            continue
#        print(i,j)
        dp[i] += dp[i-j]
        dp[i] = dp[i] % 998244353

print(dp[N])

### FIXED CODE ###

import numpy as np

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

dp = np.zeros(N+2, dtype = int)
dp[1] = 1
dp[2] = -1

atai = 0
for i in range(1, N+2):
    atai += dp[i]
    for LR in LRs:
        if(i+LR[0] <= N):
            dp[i+LR[0]] = (dp[i+LR[0]] + atai) % 998244353
        if(i+LR[1] <= N):
            dp[i+LR[1]+1] = (dp[i+LR[1]+1] -atai) % 998244353

#    print(dp)

#復元
ruisekiwa = [0]

for hoge in dp:
    ruisekiwa.append(ruisekiwa[-1]+hoge)
print(ruisekiwa[N+1] % 998244353)
### BUGGY CODE ###

s = input()

q = int(input())

for i 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 = deque(input())

q = int(input())
r = 0
for _ in range(q):
    A = list(input().split())
    if A[0] == '1':
        r = (r + 1)%2
    else:
        if (A[1] == '1' and r % 2 == 0) or (A[1] == '2' and r % 2 == 1):
            s.appendleft(A[2])
        else:
            s.append(A[2])

if r == 1:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

def calc():
  N,W=map(int,input().split())
  dp=[-1]*(W+1)
  dp[0]=0
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(W-w,-1,-1):
      if dp[j]!=-1:
        dp[j+w]=max(dp[j+w],dp[j]+v)
  print(max(dp))
  
calc()

### FIXED CODE ###

def calc():
  N,W=map(int,input().split())
  dp=[-1]*(W+1)
  dp[0]=0
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(W-w,-1,-1):
      if dp[j]!=-1:
        if dp[j+w]<dp[j]+v:
          dp[j+w]=dp[j]+v
  print(max(dp))
  
calc()
### BUGGY CODE ###

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

for i in range(Q):
  BC = list(map(int, input().split()))
  B_i = BC[0]
  C_i = BC[1]
  B_ind = []
  for j in range(len(A)):
    if A[j] == B_i:
      B_ind.append(j)
    if A[j] > B_i:
      break
  for k in B_ind:
    A[k] = C_i
  A = sorted(A)
  print(sum(A))
  

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
dic = dict()
 
for i in A:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1
 
ans = sum(A)
 
for i in range(Q):
    b, c = list(map(int, input().split()))
    x = 0
    if b in dic:
        x = dic.pop(b)
        if c in dic:    
            dic[c] += x
        else:
            dic[c] = x
    ans += x * (c-b)
    print(ans)
### BUGGY CODE ###

N = int(input())
primes = [2]
res = []
for i in range(3, 55556):
  p = len(primes)
  f = 1
  for j in range(p):
    if i % primes[j] == 0:
      f = 0
  if f:
    primes.append(i)
for q in primes:
  if q % 5 == 1:
    res.append(q)
  if len(res) == N:
    break
print(*res)

### FIXED CODE ###

N = int(input())
primes = [2]
res = []
for i in range(3, 55556):
  p = len(primes)
  f = 1
  for j in range(p):
    if i % primes[j] == 0:
      f = 0
  if f:
    primes.append(i)
    if i % 5 == 1:
      res.append(i)
  if len(res) == N:
    print(*res)
    break
### BUGGY CODE ###

import math

n=int(input())

XY=[]

for i in range(n):
    x,y=map(int,input().split())
    XY.append([x,y])

v=[]

for i in range(n):
    for j in range(n):
        if j!=i and [XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]] not in v:
            v.append([XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]])


c=0
for vx,vy in v:
    cv=0
    for i in range(n):
        for j in range(n):
            if j!=i and [XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]]==[vx,vy]:
                cv+=1
    c=max(cv,c)

print(n-c)

### FIXED CODE ###

import math

n=int(input())

XY=[]

for i in range(n):
    x,y=map(int,input().split())
    XY.append([x,y])

v=[]

for i in range(n):
    for j in range(n):
        if j!=i:
            v.append([XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]])


c=0
for vx,vy in v:
    cv=0
    for i in range(n):
        for j in range(n):
            if j!=i and [XY[i][0]-XY[j][0],XY[i][1]-XY[j][1]]==[vx,vy]:
                cv+=1
    c=max(cv,c)

print(n-c)
### BUGGY CODE ###

N = int(input())

results, counts = [], []
for i in range(1, 31):
    for j in range(1, i + 1):
        for k in range(1, j + 1):
            result = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
            results.append(result)
            if i == j and j == k:
                counts.append(1)
            elif i == j or j == k:
                counts.append(3)
            else:
                counts.append(6)

for n in range(1, N + 1):
    count = 0
    for i in range(len(results)):
        if results[i] == n:
            count += counts[i]
    print(count)

### FIXED CODE ###

N = int(input())

counts = [0] * 10001
for i in range(1, 101):
    for j in range(1, i + 1):
        for k in range(1, j + 1):
            result = i ** 2 + j ** 2 + k ** 2 + i * j + j * k + k * i
            if result > 10000:
                continue
            if i == j and j == k:
                counts[result] += 1
            elif i == j or j == k:
                counts[result] += 3
            else:
                counts[result] += 6

for n in range(1, N + 1):
    print(counts[n])
### BUGGY CODE ###

from collections import defaultdict

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

highs = list(map(int, input().split()))
towers = list(range(n))

d = defaultdict(list)

for i in range(m):
    v = list(map(int, input().split()))
    d[v[0]].append(v[1])
    d[v[1]].append(v[0])

count = 0
for k, v in d.items():
    nums = []
    
    if towers.count(k-1) > 0:
        towers.remove(k-1)
    for i in v:
        nums.append(highs[i-1])
    if highs[k-1] > max(nums):
        count += 1

print(count+len(towers))

### FIXED CODE ###

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

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

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

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

import copy

N = int(input())
list_S = [input() for i in range(N) ]
list_S.sort()
list_a = []
a = 0
for i in range(N-1):
    if list_S[i] == list_S[i+1]:
        a += 1
    else:
        list_a.append(a+1)
        a = 0
list_a.append(a+1)
newlist_a = sorted(list_a,reverse=True)
n = newlist_a.count(newlist_a[0])
ans = ""
if n == 1:
    t = list_a.index(newlist_a[0])
    m = 0
    for i in range(t):
        m += list_a[i]
    ans +=list_S[m+t]
else:
    if newlist_a[0]==1:
        for i in range(len(list_S)):
            ans += list_S[i]
            ans += "\n"
    else:            
        list_A = copy.copy(list_a)
        list_t = []
        list_t.append(list_A.index(newlist_a[0]))
        for i in range(n-1):
            list_A.remove(newlist_a[i])
            m = 0
            for j in range(list_A.index(newlist_a[i])+i+1):
                m += list_a[j]
            list_t.append(m)
        for i in range(len(list_t)):
            ans += list_S[list_t[i]]
            ans += "\n"
print(ans)

### FIXED CODE ###

import collections

N = int(input())
S = [input() for i in range(N)]
c =collections.Counter(S)
C = c.most_common()
list_C = []
for i in range(len(c)):
    list_C.append(C[i][1])
m = 1
for i in range(len(list_C)-1):
    if list_C[i]==list_C[i+1]:
        m += 1
    else:
        break
ans= []
for i in range(m):
    ans.append(C[i][0])
ans = sorted(ans)
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

import copy
n=int(input())
l=[int(input()) for x in range(n)]
ans=[]
for i in range(n):
    ans=copy.copy(l)
    ans.remove(l[i])
    print(max(ans))
    ans.clear()

### FIXED CODE ###

import copy
n = int(input())
l=[int(input()) for x in range(n)]
ll=copy.copy(l)
ll.sort()
setl=list(set(l))
setl.sort()
m=max(l)

for i in range(n):
    if len(setl)==1:
        print(m)
    else:
        second=ll[-2]
        if l[i]==m:
            print(second)
        else:
            print(m)
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
cnt=0
tmp=0
ans=0
for i in range(N-K+1):
	#print(P[i:i+K])
	if cnt<sum(P[i:i+K]):
		cnt=sum(P[i:i+K])
		tmp=i
	else:
		cnt=cnt
	#print(cnt)
for i in range(tmp,tmp+K):
	ans+=(P[i]*(P[i]+1)/2/P[i])
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
E=[0]*N

for i in range (N):
	E[i]=((P[i]+1)/2)

L=[0]*(N+1)
L[0]=0

for i in range (N):
	L[i+1]=L[i]+E[i]

ans=0

for i in range (K,N+1):
	ans=max(ans,L[i]-L[i-K])

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

def chmin(a, b):
    if a > b:
        a = b
    return a

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

dp = [10**9+10]*n
dp[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i + j < n:
            dp[i+j] = chmin(dp[i+j], dp[i]+abs(h[i]-h[i+j]))

print(dp[-1])

### FIXED CODE ###

def chmin(a, b):
    if a > b:
        a = b
    return a

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

dp = [10**9+10]*n
dp[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i + j < n:
            dp[i+j] = chmin(dp[i+j], dp[i]+abs(h[i]-h[i+j]))

print(dp[-1])