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

n, m = map(int, input().split())
p = []
y = []
d = {}
for i in range(m):
    p_, y_ = map(int, input().split())
    p.append(p_)
    y.append(y_)
    if p_ not in d.keys():
        d[p_] = [y_]
    else:
        d[p_].append(y_)
for i in d.keys():
    d[i] = sorted(d[i])
for i in range(m):
    print('{:06d}{:06d}'.format(p[i], d[p[i]].index(y[i]) + 1))


### FIXED CODE ###

import numpy as np
from bisect import bisect_right
# from time import time
# start = time()
n, m = map(int, input().split())
p = []
y = []
d = {i + 1: [] for i in range(n)}
# n, m = 10**5, 10**5
# p = [10**5]*m
# y = [i + 1 for i in range(m)]
for i in range(m):
    p_, y_ = map(int, input().split())
    # p_, y_ = p[i], y[i]
    p.append(p_)
    y.append(y_)
    d[p_].append(y_)
for i in d.keys():
    d[i] = sorted(d[i])
for i in range(m):
    # print('{:06d}{:06d}'.format(p[i], d[p[i]].index(y[i]) + 1))
    print('{:06d}{:06d}'.format(p[i], bisect_right(d[p[i]], y[i])))
#
# print(time() - start)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

# 互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

# aの逆元(mod M)を求める（aとMは互いに素）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M

def nCk(n,k):
    if k == 0:
        return 1
    else:
        return nCk(n-1,k-1)*n*mod_inv(k) %mod

n,a,b = LI()

ans = pow(2,n,mod)-1
ans -= nCk(n,a)
ans %= mod
ans -= nCk(n,b)
ans %= mod

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

# 互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

# aの逆元(mod M)を求める（aとMは互いに素）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M

def nCk2(n,k):
    x = [0]*(k+1)
    x[0] = 1
    for i in range(1,k+1):
        x[i] = x[i-1]*(n-k+i)*mod_inv(i) % mod
    return x[-1]

n,a,b = LI()

ans = pow(2,n,mod)-1
ans -= nCk2(n,a)
ans %= mod
ans -= nCk2(n,b)
ans %= mod

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

import math
A,B,N = map(int,input().split())
ans = 0
flag = False
for i in range(1,N+1):
    t = math.floor(A*i/B)
    s = A*math.floor(i/B)
    if t-s >= 1:
        flag = True
    if flag and t-s == 0:
        break
    ans = t-s
print(ans)

### FIXED CODE ###

A,B,N = map(int,input().split())
C = N - N%B
ans = A*(C-1)//B - A*((C-1)//B)
if B > N:
    ans = A*N//B - A*(N//B)
print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
Tcount = Counter(T)
flag = 'YES'
for n,c in Tcount.items():
    if c > D.count(n):
        flag = 'NO'
        break
print(flag)

### FIXED CODE ###

from collections import Counter
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
Tcount = Counter(T)
flag = 'YES'
Dcount = Counter(D)
for n,c in Tcount.items():
    if n not in Dcount:
        flag = 'NO'
        break
    if c > Dcount[n]:
        flag = 'NO'
        break
print(flag)
### BUGGY CODE ###

r=range;k,s=map(int,input().split())
print(len([0 for x in r(k+1) for y in r(k+1) for z in r(k+1) if x+y+z==s]))

### FIXED CODE ###

r=range;k,s=map(int,input().split())
print(len([0 for x in r(k+1) for y in r(k+1) if 0<=s-x-y<=k]))
### BUGGY CODE ###

import math

n = int(input())
a = [int(i) for i in input().split()]
zero = 0
total_list = [0]
total = 0
for i in a:
  total += i
  zero += total_list.count(total)
  total_list.append(total)

print(zero)


### FIXED CODE ###

import math

n = int(input())
zero = 0
total_dictionary = {0: 1}
total = 0

for i in input().split():
  total += int(i)
  zero += total_dictionary.get(total,0)
  if total in total_dictionary:
    total_dictionary[total] += 1
  else:
    total_dictionary[total] = 1

print(zero)
### BUGGY CODE ###

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

for H in range(XYH[-1][2],XYH[-1][2]+110):
    for Cx in range(101):
        for Cy in range(101):
            if all(h==max(H-abs(x-Cx)-abs(y-Cy),0) for x,y,h in XYH):
                a=H;b=Cx;c=Cy
                break
print(b,c,a)

### FIXED CODE ###

N=int(input())
XYH=list(list(map(int,input().split())) for _ in range(N))
XYH.sort(key=lambda x: -x[2])

for H in range(XYH[0][2],XYH[0][2]+110):
    for Cx in range(101):
        for Cy in range(101):
            if all(h==max(H-abs(x-Cx)-abs(y-Cy),0) for x,y,h in XYH):
                a=H;b=Cx;c=Cy
                break
print(b,c,a)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
m=float("inf") 

for i in range(1,n):
  m = min(abs(sum(a[:i]) - sum(a[i:])),m)
print(int(m))


### FIXED CODE ###

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

x=a[0]
y=sum(a[1:])
m=abs(x - y)

i=1

while i < n-1:
  x+=a[i]
  y-=a[i]
  m = min(abs(x - y),m)
  i+=1
print(m)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import itertools


def solve(N: int, L: "List[int]"):
    cnt=0
    for s in itertools.combinations(L, 3):
        a, b, c = s
        if (a < b + c) and (b < a + c) and (c < a + b):
            cnt+=1
    return cnt


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, L))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import bisect


def solve(N: int, L: "List[int]"):
    L.sort()
    cnt=0
    for a_i in range(N):
        for b_i in range(a_i+1, N):
            c_r = bisect.bisect_left(L, L[a_i]+L[b_i])
            cnt += c_r - b_i - 1
    return cnt


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, L))

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

from sys import stdin, setrecursionlimit
input = stdin.readline

setrecursionlimit(200000)
n = int(input())
c = [0] * 4
l = list(map(int, input().split()))

for i in l:
    c[i] += 1

mem = {}


def dp(n3, n2, n1, n0):
    if n0 == n:
        return 0
    if not mem.get((n3, n2, n1, n0), None):
        ans = n
        if n3 > 0:
            ans += n3 * dp(n3 - 1, n2 + 1, n1, n0)
        if n2 > 0:
            ans += n2 * dp(n3, n2 - 1, n1 + 1, n0)
        if n1 > 0:
            ans += n1 * dp(n3, n2, n1 - 1, n0 + 1)
        ans /= n - n0
        mem[(n3, n2, n1, n0)] = ans
    return mem[(n3, n2, n1, n0)]


print(dp(*c[::-1]))

### FIXED CODE ###

"""
https://atcoder.jp/contests/dp/tasks/dp_j
"""
from sys import stdin
input = stdin.readline

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

for i in l:
    c[i] += 1

dp = [[[0.0] * (n + 1) for i in range(n + 1)] for j in range(n + 1)]
dp[0][0][0] = 0
for n3 in range(0, c[3] + 1):
    for n2 in range(0, c[2] + c[3] - n3 + 1):
        for n1 in range(0, n-c[0]- n3 - n2 + 1):
            if n1 == n2 == n3 == 0:
                continue
            temp = n
            if n1 != 0:
                # temp += n1 * dp[(n1 - 1, n2, n3)]
                temp += n1*dp[n1 - 1][n2][n3]
            if n2 != 0:
                # temp += n2 * dp[(n1 + 1, n2 - 1, n3)]
                temp += n2*dp[n1 + 1][n2 - 1][n3]
            if n3 != 0:
                # temp += n3 * dp[(n1, n2 + 1, n3 - 1)]
                temp += n3*dp[n1][n2 + 1][n3 - 1]
            dp[n1][n2][n3] = temp / (n1 + n2 + n3)

print(dp[c[1]][c[2]][c[3]])
### BUGGY CODE ###

from itertools import combinations

def count(x1,y1,x2,y2):
    res = 0
    for i in range(N):
        s1 = x[i]
        s2 = y[i]
        if x1 <= s1 <= x2 and y1 <= s2 <= y2:
            res += 1
    return res 

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

x = []
y = []
y_dict = {}

for i in range(N):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
    y_dict[a] = b

number = [i for i in range(N)]
x_2 = sorted(x)
ans = 10**20

for i,j in list(combinations(number,2)):
#for i in range(len(x_2)-1):#長方系の左の辺をx座標を取得し,固定
#    for j in range(i+1,len(x_2)):#長方形の右の辺のx座標を取得し,固定

    y_list = []

    for k in range(i,j+1):#xの指定区間内にある点のy座標を取得しy_listに入れる
        y_list.append(y_dict[x_2[k]])
        
    y_list = sorted(y_list)
        

    if 2 <= len(y_list):
        #for l in range(len(y_list)-1):#yの大きい値から順に組み合わせを試す
            #for m in range(l+1,len(y_list)):
        number2 = [i for i in range(len(y_list))]
        for l,m in list(combinations(number2,2)):        
                x1 = x_2[i]
                y1 = y_list[l]
                x2 = x_2[j]
                y2 = y_list[m]
                point = count(x1,y1,x2,y2)#区間内の点の数
                
                    
                if K <= point :
                    ans = min(ans,(x2-x1)*(y2-y1)) 


               
print(ans)

### FIXED CODE ###

from itertools import combinations as comb

def count(x1,y1,x2,y2):
    res = 0
    for x,y in point:
        if x1 <= x <= x2 and y1 <= y <= y2:
            res += 1
    return res 
    
N,K = map(int,input().split())

x = []
point = []
y_dict = {}

for i in range(N):
    a,b = map(int,input().split())
    x.append(a)
    point.append((a,b))
    y_dict[a] = b#yの値はxの値と紐づけしておく

x = sorted(x)
ans = 10**20

number = [i for i in range(N)]
C = list(comb(number,2))

for i,j in C:#組合せで調べる
    y_list = []

    for k in range(i,j+1):#xの指定区間内にある点のy座標を取得しy_listに入れる
        y_list.append(y_dict[x[k]])
        
    y_list = sorted(y_list)
        

    if 2 <= len(y_list):
        number2 = [i for i in range(len(y_list))]
        C_2 = list(comb(number2,2))

        for l,m in C_2:        
                x1 = x[i]
                y1 = y_list[l]
                x2 = x[j]
                y2 = y_list[m]
                n = count(x1,y1,x2,y2)#区間内の点の数
                   
                if K <= n :
                    ans = min(ans,(x2-x1)*(y2-y1)) 
               
print(ans)
### BUGGY CODE ###

import math
k = int(input())
t = 0
for i1 in range(1, k+1):
    for i2 in range(1, k+1):
        for i3 in range(1, k+1):
            t+=math.gcd(math.gcd(i1, i2), i3)
print(t)

### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
t = 0
for i1 in range(1, k+1):
    for i2 in range(1, k+1):
        for i3 in range(1, k+1):
            t += gcd(gcd(i1, i2), i3)
print(t)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N,Q = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
PX = [tuple(map(int,input().split())) for i in range(Q)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
ps = [0] * N
for p,x in PX:
    ps[p-1] += x

ans = [0] * N
def dfs(v,p=-1):
    ans[v] = ans[p] + ps[v]
    for to in es[v]:
        if to==p: continue
        dfs(to,v)
dfs(0)
print(*ans)

### FIXED CODE ###

N,Q = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
PX = [tuple(map(int,input().split())) for i in range(Q)]

es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

xs = [0] * N
for p,x in PX:
    xs[p-1] += x

ans = [0] * N
ans[0] = xs[0]
visited = [0] * N
stack = [0]
while stack:
    v = stack.pop()
    visited[v] = 1
    for to in es[v]:
        if visited[to]: continue
        stack.append(to)
        ans[to] = ans[v] + xs[to]

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

import math

n,k = list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))
f = list(map(int, input().strip().split()))
a.sort()
f.sort()
#f = f[::-1]
af = [[] for i in range(n)]
r = 0
for i in range(n):
	af[i] = [a[n-1-i]*f[i], f[i]]
	r = max(r, af[i][0])
af.sort()
af = af[::-1]

#r = af[0][0]
l = 0
while l < r:
	c = (l+r)//2
	training = 0
	for e in af:
		if c >= e[0] or k < training:
			break
		training += (e[0]-c + e[1]-1) // e[1]
	if training <= k:
		r = c
	else:
		l = c+1
print(l)


### FIXED CODE ###

import math

n,k = list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))
f = list(map(int, input().strip().split()))
a.sort()
f.sort()
#f = f[::-1]
af = [[] for i in range(n)]
r = 0
for i in range(n):
	af[i] = [a[n-1-i]*f[i], f[i]]
	r = max(r, af[i][0])
af.sort()
af = af[::-1]

#r = af[0][0]
l = 0
while l < r:
	c = (l+r)//2
	training = 0
	for e in af:
		if c >= e[0] or k < training:
			break
		training += (e[0]-c + e[1]-1) // e[1]
	if training <= k:
		r = c
	else:
		l = c+1
print(l)
### BUGGY CODE ###

n, m = map(int,input().split())
a = [int(input()) for i in range(m)]

dp = [0] * (n+1)
dp[0] = 1

for i in range( 1, n+1):
    if i in a:
        dp[i]= 0
    else:
        dp[i]= (dp[i-1] + dp[i-2]) % 1000000007

print(dp[n])

### FIXED CODE ###

n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
a = set(a)
dp = [0] * (n+1)
dp[0] = 1

for i in range( 1, n+1):
    if i in a:
        dp[i]= 0
    else:
        dp[i]= (dp[i-1] + dp[i-2])

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

import itertools
def f(a, b):
    return max(len(str(a)), len(str(b)))
def p(n):
    l = []
    a, b = 0, 2
    while b * b <= n:
        if n % b == 0:
            n //= b
            l += [b]
        else:
            b += 1 + a
            a = 1
    if n > 1 : l += [n]
    return l

N = int(input())
l = p(N)
if len(l) < 2:
    print(f(N, 1))
else:
    w = len(l)
    ans = len(str(N))
    for i in itertools.product([0, 1], repeat=w):
        a = b = 1
        for j in range(w):
            if i[j] == 0:
                a *= l[j]
            else:
                b *= l[j]
        ans = min(ans, f(a, b))
    print(ans)

### FIXED CODE ###

import itertools
def f(a, b):
    return max(len(str(a)), len(str(b)))
def p(n):
    l = []
    a, b = 0, 2
    while b * b <= n:
        if n % b == 0:
            n //= b
            l += [b]
        else:
            b += 1 + a
            a = 1
    if n > 1 : l += [n]
    return l

def main():
    N = int(input())
    l = p(N)
    if len(l) < 2:
        print(f(N, 1))
    else:
        w = len(l)
        ans = len(str(N))
        for i in itertools.product([0, 1], repeat=w):
            a = b = 1
            for j in range(w):
                if i[j] == 0:
                    a *= l[j]
                else:
                    b *= l[j]
            ans = min(ans, f(a, b))
        print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
ans = 1
for x in a:
  ans *= x
if (ans > 1000000000000000000):
  print("-1")
else:
  print(ans)

### FIXED CODE ###

from math import *
n = int(input())
a = [int(x) for x in input().split()]
ans = 1
ok = False
fail = False
for x in a:
  if (x == 0):
    ok = True
    break
for x in a:
  if (ans * x > 1000000000000000000):
    fail = True
    break
  ans *= x
if (ok):
  print(0)
else:
  if (fail):
    print("-1")
  else:
    print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
c=s.count
r,g,b=c('R'),c('G'),c('B')
t=0
for i in range(n-2):
  for j in range(i+1,n-1):
    k=j*2-i
    if k<n:
      if s[i]+s[j]+s[k] in ('RGB','RBG','GRB','GBR','BRG','BGR'):
        t+=1
print(r*g*b-t)

### FIXED CODE ###

n=int(input())
s=input()
c=s.count
r,g,b=c('R'),c('G'),c('B')
t=0
for i in range(n-2):
  for w in range(1,(n-i+1)//2):
    if s[i]+s[i+w]+s[i+w*2] in ('RGB','RBG','GRB','GBR','BRG','BGR'):
        t+=1
print(r*g*b-t)
### BUGGY CODE ###

import copy
n = int(input())
ls = []
for i in range(n):
    a = int(input())
    ls.append(a) 

ans = max(ls)
for i in range(len(ls)):
    ls2 = copy.copy(ls)
    del ls2[i]
    if ans in ls2:
        print(ans)
    else:
        ls2.sort()
        print(ls2[-1])
    

### FIXED CODE ###

import copy
n = int(input())
ls = []
for i in range(n):
    a = int(input())
    ls.append(a) 
ls2 = copy.copy(ls)
ls.sort()
max1 = ls[-1]
max2 = ls[-2]


for i in ls2:
    if i != max1:
        print(max1)
    else:
        print(max2)
### BUGGY CODE ###

import sys

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

def minimum(S):
    T=S+S[::-1]

    ANS=[]

    for i in range(N+1):
        ANS.append(T[i:i+N])

    return min(ANS)

def next(S):
    T=S+S[::-1]
    LIST=[]
    CL=[0]*2*N
    count=0

    for i in range(2*N):
        if T[i]==MIN:
            count+=1

        else:
            count=0

        CL[i]=count

    MAX=max(CL)
    LIST=[]

    for i in range(N-1,2*N):
        if CL[i]==MAX:
            LIST.append(T[i+1-N:i+1])

    return LIST,MAX

def next2(S,x):
    return S[x:]+[MIN]*x,2*x

if K==1:
    print("".join(minimum(S)))

else:
    CAN,MAX=next(S)

    if (MAX<<(K-1))>=N:
        print(MIN*N)
        sys.exit()

    ANS=[]

    for c in CAN:
        x=MAX
        for j in range(K-2):
            c,x=next2(c,x)

            if max(c)==MIN:
                print("".join(c))
                sys.exit()

        ANS.append(minimum(c))

    print("".join(min(ANS)))

### FIXED CODE ###

import sys

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

def minimum(S):
    T=S+S[::-1]

    ANS=[]

    for i in range(N+1):
        ANS.append(T[i:i+N])

    return min(ANS)

def next(S):
    T=S+S[::-1]
    LIST=[]
    CL=[0]*2*N
    count=0

    for i in range(2*N):
        if T[i]==MIN:
            count+=1

        else:
            count=0

        CL[i]=count

    MAX=max(CL)
    LIST=[]

    for i in range(N-1,2*N):
        if CL[i]==MAX:
            LIST.append(T[i+1-N:i+1])

    return LIST,MAX

def next2(S,x):
    return [MIN]*x+S[x:][::-1]

if K==1:
    print("".join(minimum(S)))

else:
    CAN,MAX=next(S)

    if (MAX<<(K-1))>=N:
        print(MIN*N)
        sys.exit()

    ANS=[]

    for c in CAN:

        ANS.append(next2(c,MAX*((1<<(K-1))-1)))

    print("".join(min(ANS)))
### BUGGY CODE ###

H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (H + 1 + 10**4)
for i in range(1, H + 1):
    dp[i] = 10 ** 9
for i in range(H + 1):
    for a, b in ab:
        dp[i] = min(dp[i], dp[i - a] + b)
print(dp[H])


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [10**9] * (H + 1)
dp[0] = 0
for i in range(H + 1):
    for a, b in ab:
        if i - a < 0:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i - a] + b)
print(dp[H])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
a=1
if 0 in A:
    print(0)
else:
    for i in range(N):
        a*=A[i]
    if a>1000000000000000000:
        print(-1)
    else:
        print(int(a))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a=1
if 0 in A:
    print(0)
else:
    for i in range(N):
        a*=A[i]
        if a>1000000000000000000:
          print(-1)
          break
    else:
        print(int(a))
### BUGGY CODE ###

# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 24/07/2020

from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n, k = iia()
arr = iia()
dp = [0] * n
for i in range(1, n):
    cur = float("inf")
    for j in range(1, k + 1):
        if i - j >= 0:  
            t = abs(arr[i] - arr[i - j]) + dp[i - j]
            cur = min(cur, t)
        else:
            break
    dp[i] = cur
print(dp[-1])


### FIXED CODE ###

# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 24/07/2020

from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n, k = iia()
arr = iia()
dp = [0] * n
for i in range(1, n):
    cur = float("inf")
    for j in range(1, k + 1):
        if i - j >= 0:  
            t = abs(arr[i] - arr[i - j]) + dp[i - j]
            cur = min(cur, t)
        else:
            break
    dp[i] = cur
print(dp[-1])
### BUGGY CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

lmax = lambda x, y: x if len(x) > len(y) else y

@lru_cache(maxsize=10000)
def lcs(x,y):
    if x == "" or y == "":
        return ""
    elif x[-1] == y[-1]:
        return lcs(x[:-1],y[:-1]) + x[-1]
    else:
        return lmax(lcs(x[:-1],y), lcs(x,y[:-1]))

print(lcs(input(),input()))

### FIXED CODE ###

S,T = input(),input()
x,y = len(S),len(T)

dp = [[0]*(y+1) for _ in range(x+1)]

for i,s in enumerate(S):
  for j,t in enumerate(T):
    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], dp[i][j] + int(s==t))
    
a = ""
while x > 0 and y > 0:
  if dp[x][y] == dp[x-1][y]:
    x -= 1
  elif dp[x][y] == dp[x][y-1]:
    y -= 1
  else:
    x -= 1
    y -= 1
    a += S[x]

print(a[::-1])