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

import math
import bisect
from queue import Queue
from collections import deque

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

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

dp[0] = 0

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

print(dp[n-1])

### FIXED CODE ###

import math
import bisect
from queue import Queue
from collections import deque

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

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

dp[0] = 0

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

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

import numpy as np


def mo(v):
    return v % 1000000007


n = int(input())
a = mo(np.array(list(map(int, input().split()))))
s = 0
for i in range(0, n - 1, 1):
    for j in range(i + 1, n, 1):
        s += mo(a[i] * a[j])
print(mo(s))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
ans = 0
MOD = 1000000007
for i in range(0, n, 1):
    s.append((s[i] + a[i]) % MOD)

for i in range(0, n, 1):
    ans += ((s[n] - s[i + 1]) * a[i]) % MOD

print(ans % MOD)
### BUGGY CODE ###

import sys
import math
import copy
sys.setrecursionlimit(4100000)

n = int(input())
a = [int(i) for i in input().split()]
m = {}
m[0] = -1
m[1] = a[0] - m[0]/2
while True:
    m[0] += 1
    for i in range(1,n):
        m[i] = 2*(a[i-1] - m[i-1]/2)
    if (m[0] + m[n-1])//2 == a[n-1]:
        break
b = [int(m[i]) for i in m]
print(* b)

### FIXED CODE ###

import sys
import math
import copy
sys.setrecursionlimit(4100000)

n = int(input())
a = [int(i) for i in input().split()]
m = {}
m[0] = 0
m[1] = a[0] - m[0]/2
while True:
    # m[0] += 1
    for i in range(1,n):
        m[i] = 2*(a[i-1] - m[i-1]/2)
    if (m[0] + m[n-1])//2 == a[n-1]:
        break
    else:
        temp = a[n-1] - (m[0] + m[n-1])//2
        m[0] += temp

b = [int(m[i]) for i in m]
print(* b)
### BUGGY CODE ###

n = int(input())
l = [2, 1]
i = 0
while i < n:
  l.append(l[-1] + l[-2])
print(l[n-2])

### FIXED CODE ###

n = int(input())
l = [2, 1]
i = 0
while i < n:
  l.append(l[-1] + l[-2])
  i+=1
print(l[n])
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict
from math import comb
# 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(A, N):
    d1 = defaultdict(int)
    d2 = defaultdict(int)

    for i, a in enumerate(A):
        d1[i+a] += 1
    
    for i, a in enumerate(A):
        d2[i-a] += 1

    mn_x = min(min(d1.keys()), min(d2.keys()))
    mx_x = max(max(d1.keys()), max(d2.keys()))

    cnt = 0
    for x in range(mn_x, mx_x+1):
        cnt += d1[x]* d2[x]

    print(cnt)
    pass

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    main(A, N)


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict

# 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(A, N):
    d1 = defaultdict(int)
    d2 = defaultdict(int)

    for i, a in enumerate(A):
        d1[i+a] += 1
    
    for i, a in enumerate(A):
        d2[i-a] += 1

    cnt = 0
    for x in list(d1.keys())+list(d2.keys()):
        cnt += d1[x]* d2[x]

    print(cnt//2)
    pass

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    main(A, N)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            ans += gcd(i, j, k)
print(ans)

### FIXED CODE ###

import math

k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        num = math.gcd(i, j)
        for k in range(1, k+1):
            ans += math.gcd(num, k)
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
l = []
r = []
count = 0
def check(a,b,c):
    if a >= max(b) and a <= min(c):
        return 1
    else:
        return 0
for i in range(m):
    l0,r0 = map(int,input().split())
    l.append(l0)
    r.append(r0)
for y in range(n+1):
    count = count + check(y,l,r)
print(count)

### FIXED CODE ###

n,m = map(int,input().split())
l = []
r = []
for i in range(m):
    l0,r0 = map(int,input().split())
    l.append(l0)
    r.append(r0)
ans = min(r)-max(l)+1
if ans >= 0:
    print(ans)
else:
    print(0)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
s=set(a)
ans=0
for i in s:
    if a.count(i)%2==1:
        ans+=1
print(ans)


### FIXED CODE ###

import collections
n=int(input())
a=[int(input()) for i in range(n)]
s=set(a)
cnt=collections.Counter(a)
ans=0
for i in s:
    if cnt[i]%2==1:
        ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(int(input()) for i in range(n))
kami = []
a.sort()
for i in a :
    if i in kami :
        kami.remove(i)
    else :
        kami.append(i)

print(len(kami))


### FIXED CODE ###

n = int(input())
kami = set()

for i in range(n) :
    a = int(input())
    if a in kami :
        kami.remove(a)
    else :
        kami.add(a)

print(len(kami))
### BUGGY CODE ###

import sys

H, W, M = map(int, sys.stdin.readline().strip().split())

h = [0] * H
w = [0] * W

g = [[False] * W for _ in range(H)]
S = set()
for _ in range(M):
    Th, Tw = map(int, sys.stdin.readline().strip().split())

    h[Th - 1] += 1
    w[Tw - 1] += 1

    # g[Th - 1][Tw - 1] = True
    S.add((Th - 1, Tw - 1))

ans = max(h) + max(w)

index_h = [n for n, v in enumerate(h) if v == max(h)]
index_w = [n for n, v in enumerate(w) if v == max(w)]

sub = 1
# for ih in index_h:
#     for iv in index_w:
#         if g[ih][iv] is False:
#             sub = 0
#             break
#     else:
#         continue
#     break
# ans -= sub
# print(ans)


for ih in index_h:
    for iv in index_w:
        if not (ih, iv) in S:
            print(ans)
            exit()
print(ans - 1)



### FIXED CODE ###

import sys

H, W, M = map(int, sys.stdin.readline().strip().split())

h = [0] * H
w = [0] * W

# g = [[False] * W for _ in range(H)]
S = set()
for _ in range(M):
    Th, Tw = map(int, sys.stdin.readline().strip().split())

    h[Th - 1] += 1
    w[Tw - 1] += 1

    # g[Th - 1][Tw - 1] = True
    S.add((Th - 1, Tw - 1))

max_h = max(h)
max_w = max(w)
ans = max_h + max_w

index_h = [n for n, v in enumerate(h) if v == max_h]
index_w = [n for n, v in enumerate(w) if v == max_w]

sub = 1
# for ih in index_h:
#     for iv in index_w:
#         if g[ih][iv] is False:
#             sub = 0
#             break
#     else:
#         continue
#     break
# ans -= sub
# print(ans)


for ih in index_h:
    for iv in index_w:
        if not (ih, iv) in S:
            print(ans)
            exit()
print(ans - 1)
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
#import numpy as np
#import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

s=input().replace("\n","")
q=inp()

ql = []
for i in range(q):
    tmp = input()
    if tmp[0] == "1":
        ql.append("1")
    else:
        ql.append(tmp.split())

isrev=False
for i in range(q):
  if ql[i][0] == '1':
    isrev = not isrev
    continue
  if (ql[i][1] == '2') == isrev:
    s=ql[i][2]+s
  else:
    s=s+ql[i][2]
if isrev:
  s = s[::-1]

print(s)


### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
#import numpy as np
#import scipy
from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

s = input()
q = int(input())
ql = [input().split() for i in range(q)]

ans = deque(s)
isrev=False
for i in range(q):
  if ql[i][0] == '1':
    isrev = not isrev
    continue
  if (ql[i][1] == '2') == isrev:
    ans.appendleft(ql[i][2])
  else:
    ans.append(ql[i][2])

if isrev:
  ans.reverse()

s = ''.join(ans)

print(s)
### BUGGY CODE ###

import numpy as np
def solve():
    N,M = map(int, input().split())
    LR = [list(map(int, input().split())) for _ in range(M)]
    data = np.array([0 for _1 in range(N+1)])

    for i in range(M):
        data[LR[i][0]:LR[i][1]+1] += 1
    print(len(data[data==M]))



if __name__ == '__main__':
    solve()


### FIXED CODE ###

import numpy as np
def solve():
    N,M = map(int, input().split())
    LR = np.array([list(map(int, input().split())) for _ in range(M)])
    Lmax = np.max(LR[:,0])
    Rmin = np.min(LR[:,1])
    ans = Rmin - Lmax + 1 if Rmin - Lmax >=0 else 0
    print(ans)





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

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

sa = list(set(a))

if len(sa) > nk[1]:
	c = []
	for i in range(len(sa)):
		c.append(a.count(sa[i]))
		
	sc = sorted(c)
	ans = 0
	for i in range(len(sa)-nk[1]):
		ans += sc[i]
else:
	ans = 0

print(ans)


### FIXED CODE ###

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

cli = []
for i in range(nk[0]+1):
	cli.append(0)

for i in range(nk[0]):
	cli[a[i]] += 1

c = sorted(cli, reverse = True)

m = 0
for i in range(nk[1]):
	m += c[i]

ans = nk[0] - m
if ans < 0:
	ans = 0
	
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce

def comb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
    
    
r1, c1, r2, c2 = [int(i) for i in input().split()]
 
def calc(r, c):
    a = comb(r + c + 2, r + 1, mod) - r - c - 2
    b = r * (r + 3) / 2
 
    if c == 1:
        return b
    else:
        return a
 
result = calc(r2, c2) - calc(r2, c1 - 1) - calc(r1 - 1, c2) + calc(r1 - 1, c1 - 1)

if result < 0:
  result += 10**9 + 7
print(result)

### FIXED CODE ###

from operator import mul
from functools import reduce

def comb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 3 * 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
    
    
r1, c1, r2, c2 = [int(i) for i in input().split()]
 
def calc(r, c):
    a = comb(r + c + 2, r + 1, mod) - r - c - 2
    b = r * (r + 3) / 2
 
    if c == 1:
        return b
    else:
        return a
 
result = calc(r2, c2) - calc(r2, c1 - 1) - calc(r1 - 1, c2) + calc(r1 - 1, c1 - 1)
result %= mod
if result < 0:
  result += mod
print(result)
### BUGGY CODE ###

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

A1 = []
A2 = []

for i in range(N):
    A1.append(i + A[i])
    A2.append(i - A[i])

count = 0
for i in A1:
    for j in A2:
        if i ==j:
            count +=1
print(count)

### FIXED CODE ###

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

A1 = []
A2 = []

for i in range(N):
    A1.append(i + A[i])
    A2.append(i - A[i])

C_A1 = collections.Counter(A1)
C_A2 = collections.Counter(A2)
ans = 0
for i in range(N):
    ans += C_A1[i]*C_A2[i]
    
print (ans)
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]
ans[ch-1][cw-1]=0

qu = deque([])
qu.append((cw-1,ch-1))
while qu:
  x,y=qu.popleft()

  for i in range(max(x-2,0),min(x+3,w)):
    for j in range(max(y-2,0),min(y+3,h)):
      if (x==i and y==j):
        continue
      if maze[j][i]=="." and (ans[j][i]>ans[y][x] or ans[j][i]==-1):
        if (x==i and y==j+1) or (x==i+1 and y==j) or (x==i-1 and y==j) or (x==i and y==j-1):
          qu.appendleft((i,j))
          ans[j][i] = ans[y][x]
        elif ans[j][i]>ans[y][x]+1 or ans[j][i]==-1:
          ans[j][i]=(ans[y][x]+1)
          qu.appendleft((i,j))

print(ans[dh-1][dw-1])

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

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

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.appendleft([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count+=1
    if count!=4:
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
### BUGGY CODE ###

N = int(input())
C = sorted(list(map(int, input().split())))
P = int(1e9+7)

ans = 0
for i, c in enumerate(C):
    if i == N - 1:
        ans = (ans + pow(2, i, P) * c)%P
    else:
        ans = (ans + pow(2, i, P) * pow(2, N - i - 2) * (N - i + 1) * c) % P
print((ans*pow(2, N))%P)


### FIXED CODE ###

N = int(input())
C = sorted(list(map(int, input().split())))
P = int(1e9+7)

ans=0
inv2 = pow(2, P-2, P)
powa = inv2
powb = pow(2, N-1, P)
for i, c in enumerate(C):
    powa = (2*powa) % P
    powb = (inv2*powb) % P
    if i == N - 1:
        ans = (ans + powa * c)%P
    else:
        ans = (ans + powa * powb * (N - i + 1) * c) % P
print((ans*pow(2, N))%P)
### BUGGY CODE ###

from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    p_count_temp = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        while temp != 1:
            if p_count[D[temp]] == 1:
                return 0
            else:
                p_count_temp[D[temp]] = 1
            temp = temp // D[temp]
        p_count = list(np.array(p_count) + np.array(p_count_temp))
        p_count_temp = [0] * (max(A_list) + 1)
    return 1

# 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

### FIXED CODE ###

from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1

## 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
#import itertools
#import numpy as np

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

a=[0]*n
kai1 = n -1
kai2 = n -1
for i in range(n):
#    print(t.index(i+1))
    a[i]=t.index(i+1)
#print(a)
for j in range(1,n,1):
    if a[j-1] < a[j]:
        kai1 -= 1
    else:
        break
    #
for j in range(n,0,-1):
    if a[j-1] > a[j-2]:
        kai2 -= 1
    else:
        break

#print(kai1,kai2)

print(min(kai1,kai2)) 


### FIXED CODE ###

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

import math
import sys
import itertools
import numpy as np

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

a = [0]*(n)
for i in range(n):
    a[t[i]-1]=i
lmax =1
length=1

for i in range(1,n):
    if a[i] < a[i-1]:
        length = 1
    else:
        length += 1
        lmax = max(lmax,length)

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

from math import gcd
K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += gcd(gcd(i+1,j+1),k+1)

print(ans)

### FIXED CODE ###

from math import gcd
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(gcd(i,j),k)

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

N = int(input())
L = list(map(int, input().split()))
total = 0

L.sort(reverse=True)

for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        for k in range(j+1, N):
            if a - b < L[k]:
                total += 1

print(total)


### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
total = 0

for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        # j以降の項で、初めてL[k] < a-bとなるkを二分探索する
        if L[-1] > a - b:  # 一番最後の項でもOKな場合(j+1以降全部OK)
            total += N - j - 1
        elif L[j+1] <= a - b:  # 一番最初の項からNGな場合
            continue
        else:
            head = j+1  # head はL[head] > a - bを満たす(OK側)
            tail = N-1  # tail はL[tail] <= a - bを満たす(NG側)
            while head+1 != tail:
                if L[(head + tail)//2] > a - b:  # 中間地点はOK側
                    head = (head + tail) // 2
                else:  # 中間地点はNG側
                    tail = (head + tail) // 2
            total += head - j

print(total)
### BUGGY CODE ###

def minfunc(i,s,cost,p):
  iter=0
  k=i-1
  mini=abs(s[i]-s[i-1])+cost[i-1]
  while(k>=0 and iter<p):
    if abs(s[i]-s[k])+cost[k]<mini:
      mini=abs(s[i]-s[k])+cost[k]
    k=k-1
    iter=iter+1
  return mini
    
    


l=list(map(int,input().split()))
n=l[0]
p=l[1]
s=list(map(int,input().split()))
cost=[0]*n
cost[1]=abs(s[1]-s[0])
if n==2:
  
  print(abs(s[1]-s[0]))
  
else:
  for i in range(2,len(s)):
  	cost[i]=minfunc(i,s,cost,p)
  print(cost[n-1])


### FIXED CODE ###

def minfunc(i,s,cost,p):
  iter=0
  k=i-1
  mini=abs(s[i]-s[i-1])+cost[i-1]
  while(k>=0 and iter<p):
    if abs(s[i]-s[k])+cost[k]<mini:
      mini=abs(s[i]-s[k])+cost[k]
    k=k-1
    iter=iter+1
  return mini
    
    


l=list(map(int,input().split()))
n=l[0]
p=l[1]
s=list(map(int,input().split()))
cost=[0]*n
cost[1]=abs(s[1]-s[0])
if n==2:
  
  print(abs(s[1]-s[0]))
  
else:
  for i in range(2,len(s)):
  	cost[i]=minfunc(i,s,cost,p)
  print(cost[n-1])
### BUGGY CODE ###

n = int(input())
A = []
B = []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

ans = 0
for i in range(n)[-1::-1]:
    val = B[i] - A[i]%B[i]
    if val == B[i]:
        continue
    ans += val
    for j in range(i):
        A[j] += val

print(ans)

### FIXED CODE ###

n = int(input())
A = []
B = []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

ans = 0
for i in range(n)[-1::-1]:
    val = B[i] - (A[i] + ans)%B[i]
    if val == B[i]:
        continue
    ans += val
    
print(ans)
### BUGGY CODE ###

import sys
N, M = (int(i) for i in input().split())
X = [int(i) for i in input().split()]
X.sort()

pos = [[0] * 2 for i in range(N)]
total = 0

if M <= N:
    print(0)
    sys.exit()

for i in range(N):
    pos[i][0] = i
    pos[i][1] = abs(X[i+1] - X[i])
    total = total + pos[i][1]


for j in range(N, M-1):
    dim = abs(X[j+1]-X[j])
    total = total + dim
    pos = sorted(pos, key=lambda x:(x[1]))
    if pos[0][1] < dim:
        pos[0][0] = j
        pos[0][1] = dim



pos = sorted(pos, key=lambda x:(x[1]), reverse = True)
for i in range(N-1):
    total = total - pos[i][1]

print(total)


### FIXED CODE ###

import sys
N, M = (int(i) for i in input().split())
X = [int(i) for i in input().split()]
X.sort()

L = []

for i in range(1, M):
    L.append(X[i]-X[i-1])

L = sorted(L, reverse=True)

print(X[M-1]-X[0]-sum(L[:N-1]))
### BUGGY CODE ###

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

path = [1]
for _ in range(N+10):
    next_A = As[path[-1] - 1]
    if next_A in path:
        break
    else:
        path.append(next_A)

before_loop = path.index(next_A)
loop_len = len(path) - before_loop

if K <= before_loop:
    print(path[K])
else:
    print(path[(K - before_loop) % loop_len + before_loop])


### FIXED CODE ###

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

appeared = [False] * N
appeared[0] = True
path = [1]
for _ in range(N+10):
    next_A = As[path[-1] - 1]
    if appeared[next_A-1]:
        break
    else:
        path.append(next_A)
        appeared[next_A-1] = True

before_loop = path.index(next_A)
loop_len = len(path) - before_loop

if K <= before_loop:
    print(path[K])
else:
    print(path[(K - before_loop) % loop_len + before_loop])
### BUGGY CODE ###

a, b, c, d = map(int, input().split())
res = 0
for i in range(a, b+1):
  if i%c != 0 and i%d != 0:
    res += 1
print(res)

### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())
Cdiv = B // C - (A - 1) // C
Ddiv = B // D - (A - 1) // D
gcd_CD = int(C * D / fractions.gcd(C, D))
CDdiv = B // gcd_CD - (A - 1) // gcd_CD
result = int(B - (A - 1) - Cdiv - Ddiv + CDdiv)
print(result)