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

H,W,D = map(int, input().split())
fields = []
amaris = [[0] * (H*W) for i in range(D)] # あまり
for i in range(H):
    row = list(map(int, input().split()))
    # あまりがいくつかで分類
    for j,e in enumerate(row):
        n = (e-1) // D
        m = (e-1) % D
        amaris[m][n] = (i,j)

# print(amaris[:10])

Q = int(input())
for i in range(Q):
    l,r  = map(int, input().split())
    m = (l-1) % D
    s = (l-1) // D
    g = (r-1) // D
    coords = amaris[m][s:g+1]
    ans = 0
    x_pre,y_pre = coords[0]
    for x, y in coords[1:]:
        ans += abs(x-x_pre)+abs(y-y_pre)        
        x_pre = x
        y_pre = y
    print(ans)


### FIXED CODE ###

H,W,D = map(int, input().split())
fields = []
amaris = [[0] * (H*W//D+1) for i in range(D)] # あまり
for i in range(H):
    row = list(map(int, input().split()))
    # あまりがいくつかで分類
    for j,e in enumerate(row):
        n = (e-1) // D
        m = (e-1) % D
        amaris[m][n] = (i,j)

# あまりごとに累積和を取っておく
acc = [[0] * (H*W//D+1) for i in range(D)]
for i in range(D):
    cnt = 0
    x_pre, y_pre = amaris[i][0]
    for j in range(1,(H*W)//D+1):
        coords = amaris[i][j]
        if isinstance(coords,int): break
        x = coords[0]
        y = coords[1]
        cnt += abs(x-x_pre)+abs(y-y_pre)
        acc[i][j] = cnt
        x_pre = x
        y_pre = y
# print(acc)

Q = int(input())
for i in range(Q):
    l,r  = map(int, input().split())
    m = (l-1) % D
    s = (l-1) // D
    g = (r-1) // D
    ans = acc[m][g] - acc[m][s]
    print(ans)
### BUGGY CODE ###

import itertools as iter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    nums = [0] * (N+1)
    for i in A:
        nums[i] += 1
    
    comb = [0] * (N+1)
    for i in range(N+1):
        comb[i] = len(list(iter.combinations(range(nums[i]), 2)))
    
    for k in range(1, N+1):
        c = comb[:]
        i = A[k-1]
        #print("k",k, "/ num", i)
        c[i] = len(list(iter.combinations(range(nums[i]-1), 2)))
        print(sum(c))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    nums = [0] * (N+1)
    for i in A:
        nums[i] += 1
    #nums = [A.count(i) for i in range(N+1)]
    comb = sum((i*(i-1)//2 for i in nums))
    for k in range(N):
        print(comb-(nums[A[k]]-1))

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

def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d



V, E=map(int,input().strip().split(' '))
inf=10**9
cost=[[inf]*V for i in range(V)]
edge=[]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
    edge.append([fr-1,to-1])
    
d=[]
for i in range(V):
    d.append(dijkstra(i))

cand=E
for i in range(E):
    fl=False
    for s in range(V):
        for t in range(V):
            if d[s][edge[i][0]]+cost[edge[i][0]][edge[i][1]]+d[edge[i][1]][t]==d[s][t]:
                cand-=1
                fl=True
                break
        if fl:
            break

print(cand)

### FIXED CODE ###

def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d



V, E=map(int,input().strip().split(' '))
inf=10**9
cost=[[inf]*V for i in range(V)]
edge=[]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
    edge.append([fr-1,to-1])
    
d=[]
for i in range(V):
    d.append(dijkstra(i))

cand=E
for i in range(E):
    fl=False
    for s in range(V):
        if d[s][edge[i][0]]+cost[edge[i][0]][edge[i][1]]==d[s][edge[i][1]]:
            cand-=1
            fl=True
            break

print(cand)
### BUGGY CODE ###

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

for i in range(len(S)):
    a = sorted(S[i])
    S[i] = ''.join(a)

S_unq = set(S)
num_list = []

for i in S_unq:
    num = S.count(i)
    num_list.append(num)

dup_list = [i for i in num_list if i > 1]
dup_num = 0
for i in dup_list:
    b = (i * (i - 1)) / 2
    dup_num += b

print(int(dup_num))


### FIXED CODE ###

N = int(input())
strs = []
for i in range(N):
    s = list(input())
    s.sort()
    strs.append(''.join(s))

d = dict.fromkeys(strs, 0)
for s in strs:
    if s in d.keys():
        d[s] += 1
    else:
        d.setdefault(s, 1)

ans = 0
for v in d.values():
    ans += (v * (v - 1)) / 2

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

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

dp = [10**10 for i in range(N+1)]
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
    for j in range(max(1, i-K+1), i+1):
        if dp[i] >= dp[j-1] + abs(h[i]-h[j-1]):
            dp[i] = dp[j-1] + abs(h[i]-h[j-1])

print(dp[N-1])
#print(dp)

### FIXED CODE ###

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

dp = [10**10 for i in range(N+1)]
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
    for j in range(max(1, i-K+1), i+1):
        if dp[i] >= dp[j-1] + abs(h[i]-h[j-1]):
            dp[i] = dp[j-1] + abs(h[i]-h[j-1])

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

from numba import jit
from sys import stdin

@jit
def num():
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j in magic:
                if i-j[0] < 0:
                    num = ans[i]+j[1]
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+j[1]
                    if ans[i-j[0]] > num:
                        ans[i-j[0]] = num
    return ans[0]
print(num())




### FIXED CODE ###

def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j, k in magic:
                if i-j < 0:
                    num = ans[i]+k
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+k
                    if ans[i-j] > num:
                        ans[i-j] = num
    return ans[0]
print(num())
### BUGGY CODE ###

a, b = map(int, input().split())
ans = a
for i in range(a+1, b+1):
  ans = ans^i
print(ans)

### FIXED CODE ###

a, b = map(int, input().split())
ans = 0
for i in range(4*(a//4), a):
  ans = ans^i
for i in range(4*(b//4),b+1):
  ans = ans^i

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

def z_algorithm(s):
    n = len(s)
    result = [0] * n
    j = 0
    for i in range(1, n):
        if i + result[i - j] < j + result[j]:
            result[i] = result[i - j]
        else:
            k = max(0, j + result[j] - i)
            while i + k < n and s[k] == s[i + k]:
                k += 1
            result[i] = k
            j = i
    return result


n = int(input())
s = input()
print(max(max(map(min, zip(range(n - i), z_algorithm(s[i:])))) for i in range(n - 1)))


### FIXED CODE ###

def z_algorithm(s):
    n = len(s)
    prefix = [0] * n
    j = 0
    ret = 0
    for i in range(1, n):
        if i + prefix[i - j] < j + prefix[j]:
            prefix[i] = prefix[i - j]
        else:
            k = max(0, j + prefix[j] - i)
            while i + k < n and s[k] == s[i + k]:
                k += 1
            prefix[i] = k
            ret = max(ret, min(i, k))
            j = i
    return ret


n = int(input())
s = input()
print(max(z_algorithm(s[i:]) for i in range(n - 1)))
### BUGGY CODE ###

n = int(input())
i = 1
ans = 0
while 1:
    if (n-i)%i == 0 :
        if ((n-i)//i) > i:
            ans += (n-i)//i
        else:
            break
    i += 1
print(ans)

### FIXED CODE ###

n = int(input())
i = 1
ans = 0
r = int(n**(1/2))
for i in range(1,r+1):
    if (n-i)%i == 0:
        if ((n-i)//i) > i:
            ans += (n-i)//i
        else:
            break
print(ans)
### BUGGY CODE ###

H,W,M = map(int, input().split())
mx=[0] * W
my=[0] * H
bs =[]
mxx = 0
myy = 0
for i in range(M):
    y,x = map(int, input().split())
    mx[x-1] += 1
    my[y-1] += 1
    mxx = max(mx[x-1], mxx)
    myy = max(my[y-1], myy)
    bs.append((x-1,y-1))

vx = []
vy = []
for i,x in enumerate(mx):
    if x == mxx:
        vx.append((i,x))
for i,y in enumerate(my):
    if y == myy:
        vy.append((i,y))

a = 1
for i in vx:
    for j in vy:
        if (i[0],j[0]) not in bs:
            a = 0
            break
ans = vx[0][1]+vy[0][1]-a
print(ans)


### FIXED CODE ###

H,W,M = map(int, input().split())
mx=[0] * W
my=[0] * H
bs ={}
mxx = 0
myy = 0
for i in range(M):
    y,x = map(int, input().split())
    mx[x-1] += 1
    my[y-1] += 1
    mxx = max(mx[x-1], mxx)
    myy = max(my[y-1], myy)
    if y-1 in bs:
        bs[y-1].add(x-1)
    else:
        bs[y-1] = set([x-1])

vx = []
vy = []
for i,x in enumerate(mx):
    if x == mxx:
        vx.append(i)
for i,y in enumerate(my):
    if y == myy:
        vy.append(i)

a = 1

for i in vx:
    for j in vy:
        if i not in bs[j]:
            a = 0
            break
    else:
        continue
    break

ans = mxx + myy - a
print(ans)
### BUGGY CODE ###

N, X, Y = map(int, input().split())

dis = {}
for k in range(1, N):
    dis[k] = 0

for i in range(1, N):
    for j in range(i + 1, N + 1):
        d1 = abs(i - j)
        d2 = abs(i - X) + 1 + abs(j - Y)
        d3 = abs(i - Y) + 1 + abs(j - X)
        d = min(d1, d2, d3)

        dis[d] += 1

for k in range(1, N):
    print(dis[k])


### FIXED CODE ###

N, X, Y = map(int, input().split())

dis = [0 for _ in range(N)]
for i in range(1, N):
    for j in range(i + 1, N + 1):
        d = min(abs(i - j),
                abs(i - X) + 1 + abs(j - Y),
                abs(i - Y) + 1 + abs(j - X))
        dis[d] += 1

for k in range(1, N):
    print(dis[k])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
lis = [0] * N
for i in range(1, N+1):
  x = A.index(i)
  lis[i-1] = str(x+1)
ans = " ".join(lis)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
lis = [0] * N
k = 1
for i in A:
  lis[i-1] = k
  k += 1
lis = map(str, lis)
ans = " ".join(lis)
print(ans)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

class nCrMod():
  def __init__(self,n):
    self.n=n
    self.fact=[0]*(n+1)
    self.ifact=[0]*(n+1)
    self.fact[0]=1  
    for i in range(1,n+1):
      self.fact[i]=self.fact[i-1]*i
      self.fact[i]%=mod
    self.ifact[n]=pow(self.fact[n],mod-2,mod)
    for i in range(1,n+1)[::-1]:
      self.ifact[i-1]=self.ifact[i]*i
      self.ifact[i-1]%=mod
  def comb(self,n,k):
    if k<0 or n<k:
      return 0
    return self.fact[n]*self.ifact[k]*self.ifact[n-k]%mod

def main():
  n,m,k=LI()
  c=nCrMod(200005)
  ans=0
  col=m
  for x in range(n)[::-1]:
    now=col
    now*=c.comb(n-1,x)
    if x<=k:
      ans+=now
      ans%=mod
    col*=m-1
  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  fac[i]=fac[i-1]*i%mod
  inv[i]=-inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

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

def main():
  n,m,k=LI()
  res=0
  tmp=m*pow(m-1,n-k-1,mod)
   
  for r in range(n-k-1,n):
    res=(res+tmp*com(n-1,r)%mod)%mod
    tmp=tmp*(m-1)%mod
  return res

# main()
print(main())
### BUGGY CODE ###

N, K = map(int, input().split())
MOD = 998244353

nums = []

for i in range(K):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        nums.append(j)
nums.sort()
# print(nums)


dp = [0] * (N + 1)
dp[1] = 1
for i in range(2, N + 1):
    for n in nums:
        if i > n:
            dp[i] += dp[i - n]
        else:
            break

print(dp[-1]%MOD)


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353

nums = []

for i in range(K):
    l, r = map(int, input().split())
    nums.append([l, r])
# nums.sort()
# print(nums)


dp = [0] * (N + 1)
dp[1] = 1
cumsum = [0, 1]

for i in range(2, N + 1):
    for l, r in nums:
        # print(l,r)
        if i - l > 0:
            # print(i, l, r)
            # r = min(r, N)
            dp[i] += (cumsum[i - l] - cumsum[max(i - r - 1, 0)]) % MOD
    cumsum.append(cumsum[-1] + dp[i])

print(dp[-1] % MOD)
# print(dp)
# print(cumsum)
### BUGGY CODE ###

n,k = map(int,raw_input().split(' '))
arr = []
a_count = {}
for i in xrange(n):
    a,b = map(int,raw_input().split(' '))
    if not a in arr:
        arr.append(a)
        a_count.update({a:b})
    else:
        a_count[a] += b
        
        
arr.sort()
cnt = 0

for i in arr:
    cnt += a_count[i]
    if k <=cnt:
        print i
        break



### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
array = [0]*(10**5+1)
for _ in range(N):
    a, b = map(int, input().split())
    array[a] += b
ans = 0
for i in range(10**5+1):
    K -= array[i]
    if K<= 0:
        ans = i
        break
print(ans)
### BUGGY CODE ###

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

H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}

from collections import deque

def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}

from collections import deque

def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

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

#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, k = list(map(int,ipti().split()))
    h = list(map(int,ipti().split()))
    dp = [INF] * n
    dp[0] = 0

    for i in range(1, n):
        for j in range(1, k+1):
            if i - j >= 0:
                temp = abs(h[i] - h[i-j]) + dp[i-j]
                dp[i] = min(dp[i], temp)

    print(dp[n-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, k = list(map(int,ipti().split()))
    h = list(map(int,ipti().split()))
    dp = [INF] * n
    dp[0] = 0

    for i in range(1, n):
        for j in range(1, k+1):
            if i - j >= 0:
                temp = abs(h[i] - h[i-j]) + dp[i-j]
                dp[i] = min(dp[i], temp)

    print(dp[n-1])

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

def attackSurvival(n,k,q):
    points = [k]*n
    for i in range(q):
        a = int(input())-1
        for j in range(n):
          if j!=a:
            points[j] -= 1
            
    for j in range(n):
      if points[j]<=0:
        print("No")
      else:
        print("Yes")
        
(n,k,q) = map(int,input().split(" "))
attackSurvival(n,k,q)

### FIXED CODE ###

def attackSurvival(n,k,q):
    points = [k]*n
    p = [q]*n

    for i in range(q):
        a = int(input())-1
        p[a]-=1
    
    res = ""
    for j in range(n):
        if points[j]<=p[j]:
            res+="No\n"
        else:
            res+="Yes\n"
    print(res)
(n,k,q) = map(int,input().split(" ")) 
attackSurvival(n,k,q)
### BUGGY CODE ###

# （高速化）貰うDP
N,K=map(int,input().split())
h=[int(_) for _ in input().split()]

dp=[0]*(N)

for n in range(1,N):
    dp[n]=min([dp[k] + abs(h[n] - h[k]) for k in range(max(0,n-K), n)])
print(dp[N-1])

### FIXED CODE ###

# 貰うDP
N,K=map(int,input().split())
h=list(map(int,input().split()))
INF=10**9
dp=[INF]*(N)
dp[0]=0

for n in range(1,N):
    dp[n]=min([dp[k] + abs(h[n] - h[k]) for k in range(max(0,n-K), n)])
print(dp[N-1])
### BUGGY CODE ###

#!/usr/bin/env python

def gcd(a, b):
    if a < b:
        a, b = b, a

    m = a % b
    if m == 0:
        return b
    return gcd(b, m)


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

    S = input()
    T = input()
    L = N * M // gcd(N, M)
    a1 = L // N
    a2 = L // M
    cc = a1 * a2 // gcd(a1, a2)
    for i in range(L):
        if i % cc != 0:
            continue
        if S[i // a1] != T[i // a2]:
            print(-1)
            return
    print(L)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python

def gcd(a, b):
    if a < b:
        a, b = b, a

    if b == 1:
        return 1
    m = a % b
    if m == 0:
        return b
    return gcd(b, m)


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

    S = input()
    T = input()
    L = N * M // gcd(N, M)
    a1 = L // N
    a2 = L // M
    cc = a1 * a2 // gcd(a1, a2)
    for i in range(0, L, cc):
        if S[i // a1] != T[i // a2]:
            print(-1)
            return
    print(L)


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

a,b = map(int,input().split())

dp = [0 for i in range(b+10**6)]

for i in range(a):
	w,h = map(int,input().split())
	for j in range(b+10**6-1,w-1,-1):
		dp[j] = max(dp[j],dp[j-w] + h)

print(max(dp[:b+1]))

### FIXED CODE ###

a,b = map(int,input().split())

dp = [0 for i in range(b+1)]

for i in range(a):
	w,h = map(int,input().split())
	for j in range(b,w-1,-1):
		dp[j] = max(dp[j],dp[j-w] + h)

print(max(dp))
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #bfs
    for dy, dx in move1:
        childy = py + dy
        childx = px + dx
        if 0 <= childx < w and 0 <= childy < h:
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.append([childy, childx])

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            warpx = px + dx
            warpy = py + dy
            if 0<=warpx<w and 0<=warpy<h:
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])

ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        if 0 <= px+dx < w and 0 <= py+dy < h:
            childy = py + dy
            childx = px + dx
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            if 0 <= px+dx < w and 0 <= py+dy < h:
                warpx = px + dx
                warpy = py + dy
                if s[warpy][warpx] == "." and meiro[warpy][warpx] == inf:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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