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

if __name__ == '__main__':
    N,Q=list(map(int,input().split()))
    events=[list(map(int,input().split())) for _ in range(N)]
    D=[int(input()) for i in range(Q)]
    ans=[-1]*Q
    skip=[-1]*Q
    events.sort(key=lambda x:x[2])
    import bisect
    for S,T,X in events:
        right=bisect.bisect_left(D,T-X)
        left=bisect.bisect_left(D,S-X)
        while left<right:
            if skip[left]==-1:
                ans[left]=X
                skip[left]=right
                left+=1
            else:
                left=skip[left]
    for i in ans:
        print(i)


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline


n, q = map(int, input().split())
events = [list(map(int, input().split())) for _ in range(n)]
events.sort(key=lambda x: x[2])

departures = [int(input()) for _ in range(q)]


ans = ['-1'] * q
skip = [-1] * q

for start, end, pos in events:
    left = bisect.bisect_left(departures, start-pos)
    right = bisect.bisect_left(departures, end-pos)

    while left < right:
        if skip[left] == -1:
            ans[left] = str(pos)
            skip[left] = right
            left += 1

        else:
            left = skip[left]

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

N = int(input())
arr = list(map(int,input().split()))
k = 10**9+7
count = 0
for i in range(N-1):
    for j in range(i+1,N):
        count += arr[i]*arr[j]
        count = count%k
print(count)


### FIXED CODE ###

N = int(input())
arr1 = list(map(int,input().split()))
arr2 = [0 for _ in range(N)]
sum = 0
for i in range(N):
    arr2[i] = sum+arr1[i]
    sum = arr2[i]

k = 10**9+7

count = 0
for i in range(N-1):
    count += arr2[i]*arr1[i+1]
    count %= k

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

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


Con = 10**18
# ans = functools.reduce(lambda a,b: a*b,A)
# print(ans if ans<=Con else "-1")

ans = math.prod(A)
print(ans if ans<=Con else "-1")

### FIXED CODE ###

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

Con = 10**18

ans = 1
if A.__contains__(0):
    print(0)
else:
    for i in A:
        if ans <=Con:
            ans*=i
        else:
            break
    print(ans if ans<=Con else "-1")
### BUGGY CODE ###

N, X = map(int, input().split())
x = list(map(int, input().split()))
d = []

for item in x:
  d.append(abs(X- item))

m = min(d)
ans = 0

for i in range(m, 0, -1):
  flag = 1
  for j in range(N):
    if(d[j] % i != 0):
      flag = 0
      break
  if(flag == 1):
    ans = i
    break
  
print(ans)

### FIXED CODE ###

def gcd(a, b):
  if(a == b):
    return a
  elif(a % b == 0):
    return b
  elif(b % a == 0):
    return a
  elif(a == 1 or b == 1):
    return 1
  elif(a > b):
    return gcd(a- a// b* b, b)
  elif(a < b):
    return gcd(a, b- b// a* a)

def ggcd(lista):
  if(len(lista) == 1):
    return lista.pop()
  else:
    l = lista.pop()
    for i in range(1, len(lista)):
      l = gcd(l, lista.pop())
    return l

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
d = []
gcds = set()
x.sort()

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

gcds.add(d[0])

for i in range(N- 1):
  if(d[i+ 1] != d[i]):
    gcds.add(d[i+ 1])

print(ggcd(gcds))
### BUGGY CODE ###

import sys

input = sys.stdin.readline
R, C, K = map(int, input().split())
rcv = [tuple(map(int, input().split())) for _ in range(K)]
values = [[0]*C for _ in range(R)]
for r, c, v in rcv:
    values[r-1][c-1] = v

dp = [[[0]*4 for _ in range(C)] for _ in range(R+1)] # [r, c, とったアイテム]のvの最大値

for r in range(R-1, -1, -1):
    dp[r][C - 1][0] = dp[r + 1][C - 1][3]
    for i in range(1, 4):
        dp[r][C-1][i] = dp[r + 1][C-1][3]+values[r][C-1]
    for c in range(C-2, -1, -1):
        v = values[r][c]
        for i in range(4):
            if i == 0:
                dp[r][c][i] = max([dp[r+1][c][3], dp[r][c+1][i]])
            else:
                dp[r][c][i] = max([dp[r + 1][c][3]+v, dp[r][c + 1][i], dp[r][c + 1][i-1] + v])
print(dp[0][0][3])


### FIXED CODE ###

import sys

input = sys.stdin.readline
R, C, K = map(int, input().split())
values = [[0]*C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    values[r-1][c-1] = v

dp = [[[0 for _ in range(C+1)] for _ in range(R+1)] for _ in range(4)]

for r in range(R-1, -1, -1):
    # dp[0][r][C - 1] = dp[3][r + 1][C - 1]
    # for i in range(1, 4):
    #    dp[i][r][C-1] = dp[3][r + 1][C-1][3]+values[r][C-1]
    for c in range(C-1, -1, -1):
        v = values[r][c]
        for i in range(4):
            if i == 0 or v == 0:
                dp[i][r][c] = max(dp[3][r+1][c], dp[i][r][c+1])
            else:
                dp[i][r][c] = max(dp[3][r + 1][c]+v, dp[i][r][c + 1], dp[i-1][r][c + 1] + v)

print(dp[3][0][0])
### BUGGY CODE ###

import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect
import numpy as np

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()
N, M, Q = map(int, input().split())
sum_list = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    L, R = map(int, input().split())
    sum_list[L - 1][R - 1] += 1
for i in range(N):
    sum_list[i] = list(np.cumsum(sum_list[i]))
    sum_list[i].append(0)
for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for l in range(p - 1, q):
        ans += sum_list[l][q - 1] - sum_list[l][l - 1]
    print(ans)


### FIXED CODE ###

import sys
import itertools

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()
N, M, Q = map(int, input().split())
sum_list = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    L, R = map(int, input().split())
    sum_list[L - 1][R - 1] += 1
for i in range(N):
    sum_list[i] = list(itertools.accumulate(sum_list[i]))
    sum_list[i].append(0)
for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for l in range(p - 1, q):
        ans += sum_list[l][q - 1] - sum_list[l][l - 1]
    print(ans)
### BUGGY CODE ###

def combi(y,x,p=998244353):
  s=fac[y]
  t=fac[x]
  u=fac[y-x]
  ans= (s* pow(t,p-2,p)*pow(u,p-2,p))%p
  return ans

###############################

N,M,K=map(int,input().split())
p=998244353
fac=[1,1]
for i in range(2,N+1):
  fac.append( (fac[-1]*i)%p )


ans=0
for i in range(0,K+1):
  R = ( (M%p) *pow(M-1,N-1-i,p) )%p
  L = combi(N-1,i)
  ans = (ans + (R*L)%p)%p
  
print(ans)

### FIXED CODE ###

def combi(y,x,p=998244353):
  s=fac[y]
  t=fac[x]
  u=fac[y-x]
  ans= (s* pow(t,p-2,p)*pow(u,p-2,p))%p
  return ans

###############################

N,M,K=map(int,input().split())
p=998244353
fac=[1,1]
for i in range(2,N+1):
  fac.append( (fac[-1]*i)%p )


ans=0
for i in range(0,K+1):
  R = ( (M%p) *pow(M-1,N-1-i,p) )%p
  L = combi(N-1,i)
  ans = (ans + (R*L)%p)%p
  
print(ans)
### BUGGY CODE ###

h, w = [int(i) for i in input().split()]
a = []
b = []
for i in range(h):
    a.append(list(input()))
    for j in range(w):
        if a[i][j] == "#":
            b.append([i, j])

cnt = 0
ans = [["#" for i in range(w)] for j in range(h)]
while True:
    c = []
    for i in range(len(b)):
        y = b[i][0]
        x = b[i][1]
        if y > 0:
            if a[y-1][x] != "#":
                a[y-1][x] = "#"
                c.append([y-1, x])
        if y < h-1:
            if a[y+1][x] != "#":
                a[y+1][x] = "#"
                c.append([y+1, x])
        if x > 0:
            if a[y][x-1] != "#":
                a[y][x-1] = "#"
                c.append([y, x-1])
        if x < w-1:
            if a[y][x+1] != "#":
                a[y][x+1] = "#"
                c.append([y, x+1])
    if c == []:
        break
    cnt += 1
    b = c
print(cnt)

### FIXED CODE ###

from collections import deque
import sys


H, W = [int(_) for _ in input().split()]

M = []
q = deque([])
for i in range(H):
    A = input()
    M.append(list(A))
    for j in range(W):
        if A[j] == '#':
            q.append([j, i, 0])

depth_now = 0
depth = 0
count = 0
while len(q) > 0:
    p = q.popleft()
    x = p[0]
    y = p[1]
    depth = p[2]
    if x - 1 >= 0 and M[y][x-1] == '.':
        q.append([x-1, y, depth+1])
        M[y][x-1] = '#'
    if x + 1 < W and M[y][x+1] == '.':
        q.append([x+1, y, depth+1])
        M[y][x+1] = '#'
    if y - 1 >= 0 and M[y-1][x] == '.':
        q.append([x, y-1, depth+1])
        M[y-1][x] = '#'
    if y + 1 < H and M[y+1][x] == '.':
        q.append([x, y+1, depth+1])
        M[y+1][x] = '#'
print(depth)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
for i in A:
    ans*=i
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
N=int(input())
A=list(map(int,input().split()))
if 0 in A:
    print(0)
    sys.exit()
    
ans=1
for i in A:
    ans*=i
    if ans>10**18:
        print(-1)
        sys.exit()
print(ans)
### BUGGY CODE ###

from itertools import product

X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

a = []
mXY = min(X, Y)
for i, j in product(A, B):
    a.append(i + j)
a.sort(reverse=True)
a1 = a[0:K]

ans_list = []
for i, j in product(a1, C[0:K]):
    ans_list.append(i + j)
ans_list.sort(reverse=True)

for i in range(K):
    print(ans_list[i])


### FIXED CODE ###

from itertools import product

X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

a = []
count = 0
for i in range(X):
    for j in range(Y):
        if (i+1)*(j+1) > K:
            break
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) > K:
                break
            a.append(A[i] + B[j] + C[k])

a.sort(reverse=True)

for i in range(K):
    print(a[i])
### BUGGY CODE ###

# 配るDP
def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  LRs = []
  for _ in range(K):
    (L, R) = map(int, input().split(" "))
    LRs.append((L, R))

  dp = [0] * (N+1)
  dp_sum = [0] * (N+1)
  dp[1] = 1
  dp_sum[1] = 1

  for i in range(1, N+1):
    dp_sum[i] = dp[i] + dp_sum[i-1]
    if dp_sum[i] > base:
      dp_sum[i] %= base
    for lr in LRs:
      left = i + lr[0]
      right = i + lr[1] + 1
      if left <= N:
        dp[left] += dp_sum[i]
      if right <= N:
        dp[right] -= dp_sum[i]
    
  print(dp[-1]%base)

if __name__ == "__main__":
  resolve()

### FIXED CODE ###

def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  LRs = []
  for _ in range(K):
    (L, R) = map(int, input().split(" "))
    LRs.append((L, R))

  dp = [0] * (N+1)
  dp_sum = [0] * (N+1)
  dp[1] = 1
  dp_sum[1] = 1

  for i in range(2, N+1):
    for lr in LRs:
      left = max(i - lr[1] - 1, 0)
      right = max(i - lr[0], 0)
      dp[i] += dp_sum[right] - dp_sum[left]
      if dp[i] >= base:
        dp[i] %= base
      dp_sum[i] = dp_sum[i-1] + dp[i]
  print(dp[-1])

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

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
MOD = 10 ** 9 + 7
# ---------------------------
dp = [0] * (n + 1)
dp[0] = 1
if (1 in a):
    dp[1] = 0
else:
    dp[1] = 1
# dp approach

for i in range(2, n + 1):
    if (i in a):
        #dp[i] = 0
        continue
    elif (dp[i - 1] == 0 and dp[i - 2] == 0):
        print(0)
        exit()
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


#print(dp[n] % MOD)
print(dp[n])


### FIXED CODE ###

n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
'''
a = [0] * (10 ** 5)
for i in range(m):
    a[int(input())] = 1
'''

MOD = 10 ** 9 + 7
# ---------------------------
dp = [0] * (n + 1)
dp[0] = 1
if (1 in a):
    # if (a[1] == 1):
    dp[1] = 0
else:
    dp[1] = 1
# dp approach

for i in range(2, n + 1):
    if (i in a):
        # if (a[i] == 1):
        # (x in list)で探索すると、時間がかかるっぽい
        #dp[i] = 0
        continue
    elif (dp[i - 1] == 0 and dp[i - 2] == 0):
        print(0)
        exit()
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


#print(dp[n] % MOD)
print(dp[n])
### BUGGY CODE ###

[N, K] = list(map(int, input().split()))
A = list(map(int, input().split()))
P = 1

for i in range(K):
    P = P*A[i]

st = 0
la = K

for i in range(N-K):
    if A[st] != 0:
        P2 = (P/A[st])*A[la]
    else:
        P2 = 1
        for j in range(K):
            P2 *= A[i-j+1]
    if P2 > P:
        print('Yes')
    else:
        print('No')
    st += 1
    la += 1
    P = P2


### FIXED CODE ###

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

st = 0
la = K

for i in range(N-K):
    if A[la] > A[st]:
        print('Yes')
    else:
        print('No')
    st += 1
    la += 1
### BUGGY CODE ###

def resolve():
    n, m = map(int, input().split())
    s = [[j] for j in range(n)]
    for _ in range(m):
        a,b  = map(int, input().split())
        a-=1
        b-=1
        s[a].append(b)
        s[b].append(a)
    for i in range(n):
        for j in s[i]:
            s[j]=list(set(s[j]+s[i]))

    ans=0
    for i in range(len(s)):
        ans=max(len(s[i]),ans)
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    n, m = map(int, input().split())
    s = [j for j in range(n)]
    uf=UnionFind(n)
    for _ in range(m):
        a,b  = map(int, input().split())
        a-=1
        b-=1
        uf.union(a,b)

    ans=0
    for i in range(n):
        ans=max(uf.size(i),ans)
    print(ans)
resolve()
### BUGGY CODE ###

import statistics
N = int(input())
X = list(map(int, input().split()))
for i in range(N):
    print(statistics.median(X[0:i]+X[i+1:N]))

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
t = sorted(X)

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

from collections import deque
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [[j=="#" for j in input()] for i in range(h)]
# for i in range(h):
#     a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j]:
            que.append([i, j])
            white -= 1

count = 0
loop = len(que)
add = 0
while 1:
    if white == 0:
        break
    count += 1
    loop += add
    add = 0
    for i in range(loop):
        p = que.popleft()
        add -= 1
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                white -= 1
                que.append([ny, nx])
                add += 1


print(count)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


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

n=int(input())
x=list(map(int, input().split()))
 
ans = 1
for i in x:
  ans = ans*i
  
if ans > 1000000000000000000:
  ans = -1
print(ans)


### FIXED CODE ###

n=int(input())
x=list(map(int, input().split()))
 
ans=1
if 0 in x:
  ans=0
else:
  for i in x:
    ans=ans*i
    if ans>10**18:
      ans=-1
      break
print(ans)
### BUGGY CODE ###

import numpy

N,M=map(int,input().split())
A=list(map(int,input().split()))
A2=numpy.array(A)

for _ in range(M):
    # i = A.index(max(A))
    i = A2.argmax()
    a=A2[i]>>1
    A2[i]=a

print(sum(A2))

### FIXED CODE ###

from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq
logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)

def main():
    N,M=[int(x) for x in input().split()]
    A=[-int(x) for x in input().split()]

    heapq.heapify(A)
    for _ in range(M):
        a = -heapq.heappop(A) // 2 # 最小値取得
        heapq.heappush(A, -a)
    
    print(-sum(A))

main()
### BUGGY CODE ###

from _collections import deque
def main():
    D = int(input())
    C = list(map(int,input().split()))
    S = deque([])
    for _ in range(D):
        S.append(list(map(int,input().split())))

    SELECT = deque([])
    for i in range(D):
        SELECT.append(int(input())-1)

    def score(selects):
        score = 0
        L = [0 for _ in range(26)]
        def calc(ans, select, n):
            for i, l in enumerate(L):
                if i != select:
                    ans -= C[i] * (n - L[i])
                else:
                    L[i] = n
            return ans

        for i,select in enumerate(selects):
            score += S[i][select]

            for j, l in enumerate(L):
                if j != select:
                    score -= C[j] * (i+1 - L[j])
                else:
                    L[j] = i+1
        return score

    M = int(input())
    for _ in range(M):
        i, s = map(int,input().split())
        SELECT[i-1]=s-1
        print(score(SELECT))

if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    D = int(input())
    C = list(map(int,input().split()))
    S = [list(map(int,input().split()))for _ in range(D)]

    SELECT = []
    for i in range(D):
        SELECT.append(int(input())-1)

    M = int(input())
    d = []
    q = []
    for _ in range(M):
        td, tq = map(int,input().split())
        d.append(td-1)
        q.append(tq-1)

    L_ALL = [[0]*26 for _ in range(D)]
    L = [0]*26
    ans = 0
    for i in range(D):
        ans += S[i][SELECT[i]]
        L[SELECT[i]]=i+1
        if i != 0:
            L_ALL[i] = L_ALL[i-1][:]
        L_ALL[i][SELECT[i]] = i+1
        for j in range(26):
            ans -= C[j]*(i+1-L[j])

    for i in range(M):
        day = d[i]
        before = SELECT[day]
        after = q[i]
        ans -= S[day][before]
        ans += S[day][after]
        SELECT[day] = q[i]

        if day == 0:
            tmp = 0
        else:
            tmp = L_ALL[day-1][before]
        j = day
        while 0<=j<D and L_ALL[j][before]==day+1:
            L_ALL[j][before] = tmp
            ans -= C[before]*(day+1-tmp)
            j += 1

        if day == 0:
            tmp = 0
        else:
            tmp = L_ALL[day-1][after]
        j = day
        while 0<=j<D and L_ALL[j][after]==tmp:
            L_ALL[j][after]=day+1
            ans += C[after] * (day+1-tmp)
            j += 1

        print(ans)

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

import numpy as np

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
possible = True
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if k in (i, j):
                continue
            if A[i, j] < A[i, k] + A[k, j]:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                break
            if A[i, j] > A[i, k] + A[k, j]:
                possible = False
                break
        else:
            ans += A[i, j]
print(ans if possible else -1)

### FIXED CODE ###

def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()
### BUGGY CODE ###

def LI(): return list(map(int, input().split()))
inf = float('inf')

n, k = LI()
h = LI()

# init
dp = [inf] * k + [0] * n
d = [[inf] * j + [abs(h[i+j] - h[i]) for i in range(n-j)] for j in range(1, k+1)]
# print(d)

# calc
for i in range(1, n):
    d_i = []
    for j in range(1, k+1):
        d_i_j = dp[i-j+k] + d[j-1][i]
        # print(i, j, d_i_j, i-j+k, dp[i-j+k], j-1, d[j-1][i])

        d_i.append(d_i_j)

    # print(i, d_i)

    dp[i+k] = min(d_i)
# print(dp)

print(dp[-1])
"""
"""


### FIXED CODE ###

import numpy as np
def LI(): return list(map(int, input().split()))


N, K = LI()
h = np.array(LI(), dtype='int32')
dp = np.zeros(N, dtype='int32')
 
for i in range(1, N):
  start = 0 if i < K else i-K
  dp[i] = np.min(dp[start:i] + np.abs(h[i]-h[start:i]))
 
print(dp[-1])


"""
"""