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

n,m=map(int,input().split())
def hashh(x1,y1,x2,y2):
    if x1>x2:
        x1,y1,x2,y2=x2,y2,x1,y1
    if x1==x2 and y1>y2:
        x1,y1,x2,y2=x2,y2,x1,y1
    return x1*27000000000+y1*9000000+x2*3000+y2
abc_l=[list(map(int,input().split()))for _ in range(n)]
def_l=[list(map(int,input().split()))for _ in range(m)]
x=[0]
y=[0]
for a,b,c in abc_l:
    x.append(a)
    x.append(b)
    y.append(c)
for d,e,f in def_l:
    x.append(d)
    y.append(e)
    y.append(f)
x=sorted(list(set(x)))
y=sorted(list(set(y)))
h=len(x)+1
w=len(y)+1
dicx={}
dicy={}
for i in range(len(x)):dicx[x[i]]=i
for i in range(len(y)):dicy[y[i]]=i
grid=[[0]*w for _ in range(h)]
dont=set()
for a,b,c in abc_l:
    for i in range(dicx[a],dicx[b]):
        dont.add(hashh(i+1,dicy[c],i+1,dicy[c]+1))
for d,e,f in def_l:
    for j in range(dicy[e],dicy[f]):
        dont.add(hashh(dicx[d],j+1,dicx[d]+1,j+1))
if dicx[0]==0 or dicx[0]==h-1 or dicy[0]==0 or dicy[0]==w-1:
    exit(print("INF"))
stack=[(dicx[0],dicy[0])]
grid[dicx[0]][dicy[0]]=1
ans=0
for sx,sy in stack:
    ans+=(x[sx]-x[sx-1])*(y[sy]-y[sy-1])
    for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
        tx=sx+dx
        ty=sy+dy
        if grid[tx][ty]:continue
        if hashh(sx,sy,tx,ty) in dont:continue
        if tx==0 or tx==h-1 or ty==0 or ty==w-1:
            exit(print("INF"))
        grid[tx][ty]=1
        stack.append((tx,ty))
print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
def hashh(x,y,f):
    return (x*3000+y)*2+f
abc_l=[list(map(int,input().split()))for _ in range(n)]
def_l=[list(map(int,input().split()))for _ in range(m)]
x=[0]
y=[0]
for a,b,c in abc_l:
    x.append(a)
    x.append(b)
    y.append(c)
for d,e,f in def_l:
    x.append(d)
    y.append(e)
    y.append(f)
x=sorted(list(set(x)))
y=sorted(list(set(y)))
h=len(x)+1
w=len(y)+1
dicx={}
dicy={}
for i in range(len(x)):dicx[x[i]]=i
for i in range(len(y)):dicy[y[i]]=i
grid=[[0]*w for _ in range(h)]
dont=set()
for a,b,c in abc_l:
    for i in range(dicx[a],dicx[b]):
        dont.add(hashh(i+1,dicy[c],1))
for d,e,f in def_l:
    for j in range(dicy[e],dicy[f]):
        dont.add(hashh(dicx[d],j+1,0))
if dicx[0]==0 or dicx[0]==h-1 or dicy[0]==0 or dicy[0]==w-1:
    exit(print("INF"))
stack=[(dicx[0],dicy[0])]
grid[dicx[0]][dicy[0]]=1
ans=0
for sx,sy in stack:
    ans+=(x[sx]-x[sx-1])*(y[sy]-y[sy-1])
    for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
        tx=sx+dx
        ty=sy+dy
        if grid[tx][ty]:continue
        if hashh(min(sx,tx),min(sy,ty),1 if sx==tx else 0) in dont:continue
        if tx==0 or tx==h-1 or ty==0 or ty==w-1:
            exit(print("INF"))
        grid[tx][ty]=1
        stack.append((tx,ty))
print(ans)
### BUGGY CODE ###

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

if A.count(0):
    print(0)
else:
    for a in A:
        mal = mal * a
    if mal <= 10 ** 18:
        print(mal)
    else:
        print(-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

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

    if A.count(0):
        print(0)
        return

    ans = 1
    for a in A:
        ans = ans * a
        if ans > 10 ** 18:
            print(-1)
            return
    print(ans)

Main()
### BUGGY CODE ###

N = int(input())
a = []
a = list(map(int,input().split()))
index = 0
count = 0
searchNum = 1
for j in range(N+1):
    if searchNum ==1:
        if not searchNum in a:
            searchNum = N +1
            break
    if not searchNum in a[index:N]:
        searchNum -= 1
        break
    if j + index < N:
        if a[index + j] == searchNum:
            index = index + j
            searchNum += 1
            continue
    else:
        break

print(int(N -searchNum))



### FIXED CODE ###

N = int(input())
a = []
a = list(map(int,input().split()))
index = 0
count = 0
searchNum = 1
if not 1 in a:
    count = -1
else:
    for j in range(N):

        if a[j] ==searchNum:
            searchNum += 1
            continue
        else:
            count +=1
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

A = []
B = []

for s in S:
    a = 0
    k = 0
    for i in range(len(s)):
        if s[i] == ')':
            k += 1
        else:
            k -= 1
        a = max(a, k)
    b = 0
    k = 0
    for i in range(len(s))[::-1]:
        if s[i] == '(':
            k += 1
        else:
            k -= 1
        b = max(b, k)
    A.append(a)
    B.append(b)

L = []
R = []

for i in range(N):
    if B[i] - A[i] >= 0:
        L.append((A[i], i))
    else:
        R.append((B[i], i))

L.sort()
R.sort(reverse=True)

T = ''

for a, i in L:
    T += S[i]

for b, i in R:
    T += S[i]

k = 0

for t in T:
    if t == '(':
        k += 1
    else:
        k -= 1
    if k < 0:
        print('No')
        break
else:
    if k == 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

A = []
B = []

for s in S:
    a = 0
    k = 0
    for i in range(len(s)):
        if s[i] == ')':
            k += 1
        else:
            k -= 1
        a = max(a, k)
    b = 0
    k = 0
    for i in range(len(s))[::-1]:
        if s[i] == '(':
            k += 1
        else:
            k -= 1
        b = max(b, k)
    A.append(a)
    B.append(b)

L = []
R = []

for i in range(N):
    if B[i] - A[i] >= 0:
        L.append((A[i], i))
    else:
        R.append((B[i], i))

L.sort()
R.sort(reverse=True)

T = []

for a, i in L:
    T.append(S[i])

for b, i in R:
    T.append(S[i])

T = ''.join(T)

k = 0

for t in T:
    if t == '(':
        k += 1
    else:
        k -= 1
    if k < 0:
        print('No')
        break
else:
    if k == 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
A = [10**18] * 3
B = [10**18] * 3
dg = abs(ga - gb)
ds = abs(sa - sb)
db = abs(ba - bb)
if ga < gb:
    A[0] = ga
elif ga > gb:
    B[0] = gb
if sa < sb:
    A[1] = sa
elif sa > sb:
    B[1] = sb
if ba < bb:
    A[2] = ba
elif ba > bb:
    B[2] = bb

def calc(X):
    res = -1
    for i in range(N+1):
        if X[0] * i > N:
            break
        M = N - X[0] * i
        jj = M // X[1]
        x = 300
        for j in range(max(jj - x, 0), jj+1):
            k = (M - X[1] * j) // X[2]
            res = max(res, dg * i + ds * j + db * k)
        kk = M // X[2]
        for k in range(max(kk - x, 0), kk+1):
            j = (M - X[2] * k) // X[1]
            res = max(res, dg * i + ds * j + db * k)
    return res

N += calc(A)
N += calc(B)
print(N)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
INF = 10**18
A = [INF] * 3
B = [INF] * 3
values = [abs(ga - gb), abs(sa - sb), abs(ba - bb)]
if ga < gb:
    A[0] = ga
elif ga > gb:
    B[0] = gb
if sa < sb:
    A[1] = sa
elif sa > sb:
    B[1] = sb
if ba < bb:
    A[2] = ba
elif ba > bb:
    B[2] = bb

def calc(X):
    dp = [0] * (N+1)
    dp[0] = 0
    for x, v in zip(X, values):
        for i in range(N+1-x):
            dp[i+x] = max(dp[i+x], dp[i] + v)
    return dp[-1]

N += calc(A)
N += calc(B)
print(N)
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7

ans = 0
d = 1
for _ in range(60):
    x = 0
    for i in range(n):
        x += a[i] % 2
        a[i] //= 2
    ans = (((x * (n-x)) % MOD) * d % MOD + ans) % MOD
    d = d * 2 % MOD

print(ans)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7

ans = 0
d = 1
for _ in range(60):
    x = 0
    for i in range(n):
        x += a[i] % 2
        a[i] //= 2
    ans = (((x * (n-x)) % MOD) * d % MOD + ans) % MOD
    d = d * 2 % MOD

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

import numpy as np
import sys
# import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n, k = xnxn()
a = xnxn(flag="l")
for _ in range(k):
    tmp = [0]*(n+1)
    for i in range(0, n):
        l = max(0, i - a[i])
        r = min(n, i + a[i]+1)
        tmp[l] += 1
        tmp[r] -= 1
    for i in range(1, n):
        tmp[i] += tmp[i - 1]
    if a == tmp:
        break
    a = tmp

for i in a[:n]:
    print(i, end=" ")


### FIXED CODE ###

# import numpy as np
import sys
# import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n, k = xnxn()
a = xnxn(flag="l")
for _ in range(k):
    tmp = [0]*(n+1)
    for i in range(0, n):
        l = max(0, i - a[i])
        r = min(n, i + a[i]+1)
        tmp[l] += 1
        tmp[r] -= 1
    for i in range(1, n):
        tmp[i] += tmp[i - 1]
    if a == tmp:
        break
    a = tmp

for i in a[:n]:
    print(i, end=" ")
### BUGGY CODE ###

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

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

# A[i], B[i] はまとめてしまう
stores = [list(map(int, input().split())) for n in range(N)]

# 最も安い店を探す
def getCheapest():
  cheapest = 0
  for i in range(1, N):
    if (stores[i][0] < stores[cheapest][0] and stores[i][1] > 0):
      cheapest = i
  return cheapest

remaining = M
cost = 0
while True:
  store = stores[getCheapest()]
  if store[1] >= remaining: # もしこの店で買いきれるなら
    cost += store[0] * remaining
    break
  else: #買い切れないなら
    bought = store[1]
    store[1] = 0
    cost += store[0] * bought
    remaining -= bought

print(cost)

### FIXED CODE ###

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

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

# A[i], B[i] はまとめてしまう
stores = [list(map(int, input().split())) for n in range(N)]

# 安さ順にソート
stores.sort(key = lambda s: s[0])

remaining = M
cost = 0

while True:
  store = stores[0]
  if store[1] >= remaining: # もしこの店で買いきれるなら
    cost += store[0] * remaining
    break
  else: #買い切れないなら
    cost += store[0] * store[1]
    remaining -= store[1]
    stores.pop(0)

print(cost)
### BUGGY CODE ###

import numpy as np

N = int(input())
a = list(map(int, input().split()))
a = np.sort(a)
count = 0
idxes = np.arange(len(a))
while len(idxes):
    idx = idxes[0]
    idxes = np.delete(idxes, 0)
    var = a[idx]
    amari = var % a
    if len(np.where(amari == 0)[0]) == 1:
        count += 1
    idxes = idxes[np.where(a[idxes] % var != 0)[0]]
print(count)

### FIXED CODE ###

from sys import stdin

import numpy as np

U = 10 ** 6 + 10


def main():
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    ret = 0
    exist_counts = [0] * U
    for x in a:
        if exist_counts[x]:
            exist_counts[x] = 2
            continue
        idx = x
        while idx < U:
            exist_counts[idx] += 1
            idx += x
    for x in a:
        ret += exist_counts[x] == 1
    print(ret)
main()
### BUGGY CODE ###

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

dp = [[0]*N for _ in range(K+1)]
for i in range(N):
    dp[0][i] = S[i]

for i in range(K):
    for j in range(N):
        m = max(0, j-dp[i][j])
        M = min(N, j+dp[i][j]+1)
        for k in range(m, M):
            dp[i+1][k] += 1
ans = ""
for i in range(N):
    ans += str(dp[K][i]) + " "
print(ans[:-1])

### FIXED CODE ###

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

K = min(K, 41)
dp = [[0]*N for _ in range(K)]

for i in range(N):
    temp = S[i]
    m = max(0, i-temp)
    dp[0][m] += 1
    if N > i+temp+1:
        dp[0][i+temp+1] -= 1

for i in range(K-1):
    temp = 0
    for j in range(N):
        temp += dp[i][j]
        m = max(0, j-temp)
        dp[i+1][m] += 1
        if N > j+temp+1:
            dp[i+1][j+temp+1] -= 1

ans = [0]*N
ans[0] = dp[K-1][0]

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

print(" ".join(map(str, ans)))
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
x = float("inf")

dp = [x] * n
dp[0] = 0
for i in range(1,n):
    for j in range(max(0,i-k),i):
            dp[i] = min(dp[i],abs(h[j]-h[i])+dp[j])
print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
x = float("inf")

dp = [x] * n
dp[0] = 0
for i in range(1, n):
    for j in range(max(0, i - k), i):
        dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))

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

import math

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

i = 1
maxnum = 1
while i <= N:
    if ((A * (i-1) // B) - A * ((i-1) // B)) < ((A * (i) // B) - A * ((i) // B)):
        maxnum = ((A * (i) // B) - A * ((i) // B))
        i = i + 1

print(maxnum)


### FIXED CODE ###

a, b, n = list(map(int, input().split()))
x = min(b - 1, n)
ans = int(a * x / b)
print(ans)
### BUGGY CODE ###

import fractions

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

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
  
A_list = divisor(A)
B_list = divisor(B)

box = []

for i in A_list:
  if i in B_list:
    box.append(i)

box = sorted(box)

tmp = []

for l in range(len(box)-1):
  for m in range((l+1),len(box)):
    if fractions.gcd(box[l],box[m]) != 1:
      tmp.append(box[m])
      
print(len(box)-len(set(tmp)))

### FIXED CODE ###

#l=list(map(int, input().split()))
a,b=map(int, input().split())
#l=list(map(int, input().split()))
#n = int(input())
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1



ans = 1
temp1 = divisor(a)
temp2 = divisor(b)
hoge = []
if len(temp1) < len(temp2):
    hoge = temp1
    hoge2 = temp2
else:
    hoge = temp2
    hoge2 = temp1

temp = []
for i in hoge:
    if i in hoge2:
        temp.append(i)

#print (temp)
for i in temp:
    if is_prime(i):
        ans += 1

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

n = int(input())
a = []
a_sorted = []
tmp = 0
tmpp = 0

for i in range(n):
    a.append(int(input()))

for i in range(n):
    
    tmp = a[i]
    a[i] = 0

    print(max(a))

    a[i] = tmp

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

sorted_a = sorted(a)

max_a = sorted_a[-1]
max_a_r = sorted_a[-2]

for i in range(n):
    if a[i] == max_a:
        print(max_a_r)
    else:
        print(max_a)
### BUGGY CODE ###

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

max=0
for i in range(0,N-(K-1)):
    tmp=0
    for j in range(K):
        tmp+=p[i+j]
    if tmp>max:
        max=tmp
print((max+K)*0.5)

### FIXED CODE ###

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

max=0
tmp=0
for x in range(0,K):
    max+=p[x]
    tmp+=p[x]
for i in range(K,N):
    tmp=tmp+p[i]-p[i-K]
    if tmp>max:
        max=tmp
print((max+K)*0.5)
### BUGGY CODE ###

n,q = map(int, input().split())
point_array = [list(map(int,input().split())) for i in range(n-1)]
point_array.sort()
action_array = [list(map(int,input().split())) for i in range(q)]
solution = [0]*n

for i in range(q):
    solution[action_array[i][0]-1] += action_array[i][1]

for i in range(n-1):
    solution[point_array[i][1]-1] += solution[point_array[i][0]-1]
    
print(*solution)

### FIXED CODE ###

#これ計算量一次やけどACにならんかった

n,q = map(int, input().split())
point_array = [list(map(int,input().split())) for i in range(n-1)]
action_array = [list(map(int,input().split())) for i in range(q)]

point_array.sort()
solution = [0]*n

for i in range(q):
    solution[action_array[i][0]-1] += action_array[i][1]

for i in range(n-1):
    solution[point_array[i][1]-1] += solution[point_array[i][0]-1]
    
print(*solution)
### BUGGY CODE ###

A, B, M = map(int, input().split())
# items
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# discount
d = [list(map(int,input().split())) for i in range(M)]

list = []

for i in range(M):
  if min(a) + min(b) > a[d[i][0] - 1] + b[d[i][1] - 1] - d[i][2]:
    list.append(a[d[i][0] - 1] + b[d[i][1] - 1] - d[i][2])

if len(list) != 0:
  print(min(list))
else:
  print(min(a) + min(b))

### FIXED CODE ###

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
min = min(a) + min(b)

for i in range(M):
  x, y, c = list(map(int, input().split()))
  tmp = a[x - 1] + b[y - 1] - c
  if min > tmp:
    min = tmp

print(min)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys.stdout import flush

def inpl(): return tuple(map(int, input().split()))

def ismale(S):
    if S == "Male":
        return 1
    elif S == "Female":
        return 0
    else:
        exit()

N = int(input())
print(0)
flush()

c0 = ismale(input())
w = c0

C = [0 for _ in range(N)]
if c0 == 1:
    C[::2] = [1]*(N//2+1)
else:
    C[1::2] = [1]*(N//2)

L = 0
R = N - 1
post = (R - L + 1)//2
while True:
    print(post)
    flush()
    
    if post % 2 == 1:
        c = ismale(input())
        if c != w:
            L = post + 1
        else:
            R = post - 1
    else:
        c = ismale(input())
        if c != w:
            R = post
        else:
            L = post + 1

    if R - L == 2:
        print((R-L+1)//2)
        flush()
        c = ismale(input())
        print(R)
        flush()
        c = ismale(input())
        print(L)
        flush()
        c = ismale(input())
    else:
        post = (R - L + 1)//2

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

def inpl(): return tuple(map(int, input().split()))

def ismale(S):
    if S == "Male":
        return 1
    elif S == "Female":
        return 0
    else:
        exit()

N = int(input())
print(0)
sys.stdout.flush()

c0 = ismale(input())
w = c0

C = [0 for _ in range(N)]

L = 0
R = N - 1
post = (R + L)//2
while True:
    print(post)
    sys.stdout.flush()
    
    if post % 2 == 1:
        c = ismale(input())
        if c != w:
            L = post + 1
        else:
            R = post - 1
    else:
        c = ismale(input())
        if c != w:
            R = post
        else:
            L = post

    if R - L == 2:
        print((R+L+1)//2)
        sys.stdout.flush()
        c = ismale(input())
        print(R)
        sys.stdout.flush()
        c = ismale(input())
        print(L)
        sys.stdout.flush()
        c = ismale(input())
    else:
        post = (R + L)//2
### BUGGY CODE ###

#2-1-1 #ABC104C
d,g=map(int,input().split())
q=[]
bornus=[]
for i in range(d):
    p,c=map(int,input().split())
    q.append(p)
    bornus.append(c)
from collections import defaultdict
data=defaultdict(set)
data[0]|={(0 for i in range(d)),}
def makesolve(q,k):
    before=data[k-1].copy()
    for i in before:
        ii=list(i)
        for j in range(d):
            if ii[j]<q[j]:
                ico=ii.copy()
                ico[j]+=1
                data[k]|={tuple(ico),}
    
def calc(q,bornus,solve):
    point=0
    for i in range(d):
        point+=solve[i]*(i+1)*100
        if solve[i]==q[i]:
            point+=bornus[i]
    return point

ans=sum(q)
for i in range(1,sum(q)+1):
    makesolve(q,i)
    for j in data[i]:
        if calc(q,bornus,j)>=g:
            ans=i
            break
    if ans<sum(q):break
print(ans)

### FIXED CODE ###

d,g = map(int,input().split())
q={}
comp={}
p={}
minsolve=0
for i in range(d):
    a,b=map(int,input().split())
    q[i]=a
    p[i]=100*(i+1)
    comp[i]=100*(i+1)*a+b
    minsolve+=a
    
solve=[0 for _ in range(d)]
def roop(s,check,point,solved,minsolve):
    solve=s.copy()
    solve2=s.copy()
    if check==d:
        if point>g:
            minsolve=min(minsolve,solved)
            return minsolve
        if 0 in solve:
            solverev=solve.copy()
            solverev.reverse()
            idx=d-solverev.index(0)-1
            shold=1+(g-point-1)//p[idx]
            if q[idx]>shold and shold>=0:
                solved+=shold
                minsolve=min(minsolve,solved)
        return minsolve

    minsolve=roop(solve,check+1,point,solved,minsolve)
    solve2[check]+=1
    minsolve=roop(solve2,check+1,point+comp[check],solved+q[check],minsolve)
    return minsolve

print(roop(solve,0,0,0,minsolve))
### BUGGY CODE ###

[N,K,S] = list(map(int,input().split()))
if S != 1:
    output = ""
    for i in range(K):
        output += "{} ".format(S)
    for i in range(N-K):
        output += "1 "
else:
    output = ""
    for i in range(K):
        output += "{} ".format(S)
    for i in range(N-K):
        output += "2 "

print(output[0:-1])

### FIXED CODE ###

[N,K,S] = list(map(int,input().split()))
cnt = 0
if S != 1:
    output = []
    for i in range(K):
        output.append(S)
    for i in range(N-K):
        cnt += 1
        if cnt < S:
            output.append(1)
        else:
            output.append(S+1)
            cnt = 0
else:
    output = []
    for i in range(K):
        output.append(S)
    for i in range(N-K):
        output.append(2)

print(" ".join(map(str, output)))
### BUGGY CODE ###

import numpy as np

N, W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)

for i in range(N):
    w[i], v[i] = map(int, input().split())

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

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1,j] = max(dp[i,j], dp[i,j-w[i]]+v[i])
        else:
            dp[i+1,j] = dp[i,j]


print(dp[N][W])


### FIXED CODE ###

N, W = map(int, input().split())
w = [0]*N
v = [0]*N

for i in range(N):
    w[i], v[i] = map(int, input().split())

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

for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])
### BUGGY CODE ###

#1:初期化
N, K = map(int,input().split())
h = list(map(int, input().split()))
inf = float("inf")
dp = [inf]*(N) #Kが100までなので余分に入れて安全！

#2:初期値
dp[0] = 0

#3:dp実行部(配るDP)
for i in range(N):
    for k in range(1,min(N-i-1,K)+1):
        dp[i+k] = min(dp[i+k], dp[i] + abs(h[i] - h[i+k]))
        #print(dp,i,k)

#4:出力
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*- 
def cost(h,N,K):
    dp=[0]*N
    dp[1]=abs(h[0]-h[1])
    for i in range(2,N):
        tmp=[abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i)]
        dp[i]=min(tmp)
    return dp[-1]

N,K=map(int,input().split())
h=[int(num) for num in input().split()]

print(cost(h,N,K))