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

import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
dic = {}
li = [[] for i in range(n+1)]
pyli = []
for i in range(m):
    p, y = na()
    li[p].append(y)
    pyli.append([p, y])
for yyy in li:
    yyy.sort()
for p, y in pyli:
    i = li[p].index(y)
    shi = str(p)
    num = str(i + 1)
    print(shi.zfill(6) + num.zfill(6))


### FIXED CODE ###

import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
buf = [None] * m
cnt = {k: [] for k in range(n + 1)}
for i in range(m):
    p, y = na()
    cnt[p].append((y, i))
for p, l in cnt.items():
    if not l:
        continue
    l.sort()
    for j, (y, i) in enumerate(l):
        buf[i] = '{:06d}{:06d}'.format(p, j + 1)

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

N,Q=map(int, input().split())
s=input()
td=[input().split() for i in range(Q)]

import numpy as np

S=[np.zeros(N,dtype=np.int) for i in range(26)]
for p,c in enumerate(s):
    for i in range(26):
        if i==ord(c)-65:
            S[i][p]=1

g=np.ones(N,dtype=np.int)
for q in td:
    g_stable=g*np.logical_not(S[ord(q[0])-65])
    if q[1]=='L':
        g_move=np.append((g*S[ord(q[0])-65])[1:],0)
    else:
        g_move=np.insert((g*S[ord(q[0])-65])[:-1],0,0)
    g=g_stable+g_move
print(np.sum(g))

### FIXED CODE ###

N,Q=map(int, input().split())
s=input()
td=[input().split() for i in range(Q)]

def move(s,td,position):
    p=position
    for spell in td:
        if s[p]==spell[0] and spell[1]=='L':
            p-=1
        elif s[p]==spell[0] and spell[1]=='R':
            p+=1
        if p<0 or p>=N: break
    return p

l=0
r=N-1
watched=[0]*N
while(True):
    p=(r+l)//2
    if watched[p]>0:
        if p<N-1 and watched[p+1]==0:
            p+=1
        else:
            break
    res=move(s,td,p)
    if res<0:
        l=p
        watched[p]=1
    else:
        r=p
        if watched[p]==0: watched[p]=2
ans_l=N
for i in range(N):
    if watched[i]==2:
        ans_l=i
        break

l=0
r=N-1
watched2=[0]*N
while(True):
    p=(r+l)//2
    if watched2[p]>0:
        if p<N-1 and watched2[p+1]==0:
            p+=1
        else:
            break
    res=move(s,td,p)
    if res>=N:
        r=p
        watched2[p]=3
    else:
        l=p
        if watched2[p]==0: watched2[p]=2
ans_r=-1
for i in range(N-1,-1,-1):
    if watched2[i]==2:
        ans_r=i
        break
print(max(0,ans_r-ans_l+1))
### BUGGY CODE ###

n,k=map(int,input().split())
s=list(map(int,input().split()))

lambda x:x+1/2
ans=0
tmp=0
for i in range(n-k+1):
    if tmp < sum(s[i:i+k]):
        tmp = sum(s[i:i+k])
        kukan = [i,i+k]

for i in range(kukan[0],kukan[1]):
    ans += (s[i]+1)/2
    
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
s=list(map(int,input().split()))

ans=0
tmp=0
tmp2=sum(s[0:k])
kukan=[0,n]
for i in range(n-k):
    tmp2 -= s[i]
    tmp2 += s[k+i]
    if tmp < tmp2:
        tmp = tmp2
        kukan = [i+1,i+k+1]

for i in range(kukan[0],kukan[1]):
    ans += (s[i]+1)/2
    
print(ans)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

data=[]

for i in range(0,X):
  
  for j in range(0,Y):
    
    for k in range(0,Z):
      data.append(int(A[i]+B[j]+C[k]))
    
data.sort()
data.reverse()

for l in range(K):
  print(data[l])


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
A.reverse()
B.reverse()
C.reverse()

data=[]

for i in range(0,X):
  if i+1>K: break
    
  for j in range(0,Y):
    if (i+1)*(j+1)>K: break
    
    for k in range(0,Z):
      if (i+1)*(j+1)*(k+1)>K: break
      data.append(int(A[i]+B[j]+C[k]))
        
    
data.sort()
data.reverse()

for l in range(K):
  print(data[l])
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, - 1, - 1):
    deli[i] = max(deli[i - 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, - 1, - 1):
    deli[i] = max(deli[i - 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)
### BUGGY CODE ###

N = input()
num = len(N)
mod_sum = [0 for i in range(2019)]
ans = 0
for i in range(num):
  a = int(N[i:])
  mod = a%2019
  mod_sum[mod] += 1
  if mod == 0:
    ans += 1
for i in mod_sum:
  ans += i*(i-1)//2
print(ans)


### FIXED CODE ###

N = input()
num = len(N)
mod_sum = [0]*2019
mod_sum[0] = 1
ans = 0
a = 0
d = 1
for i in range(num):
  a = (a + int(N[-i-1])*d)%2019
  d = (d*10)%2019
  mod_sum[a] += 1
for i in mod_sum:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]
S_set = list(set(S))
#print(S_set)
word_buf = []
cnt = []
mmax = -1

for i in range(len(S_set)) :
    cnt.append(S.count(S_set[i]))
    if i == 0 :
        word_buf.append(S_set[i])
    else :
        if cnt[i] < mmax :
            pass
        elif cnt[i] == mmax :
            word_buf.append(S_set[i])
        elif cnt[i] > mmax :
            word_buf.clear()
            word_buf.append(S_set[i])
    mmax = max(mmax,cnt[i]) # 現時点での最大値
word_buf = sorted(word_buf)
#print("--")
for i in range(len(word_buf)) :
    print(word_buf[i])

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [''] * N
for i in range(N) :
    S[i] = input()
S = Counter(S).most_common()
c = S[0][1]

print(*sorted([a for a,s in S if s==c]),sep="\n")
### BUGGY CODE ###

if __name__ == '__main__':
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    def multi(given_list):
        ans = 1
        for i in given_list:
            ans *= i
        return ans


    score_list = [multi(a[i:k+i]) for i in range(n - k + 1)]
    for i in range(len(score_list)-1):
        if score_list[i] < score_list[i+1]:
            print("Yes")
        else:
            print("No")

### FIXED CODE ###

if __name__ == '__main__':
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    for i in range(len(a) - k):
        if a[i] < a[i+k]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

import itertools
N = int(input())
L = list(map(int, input().split()))
A = list(itertools.combinations(L, 3))
ans = 0
for i in A:
    if i[0] >= i[1]+i[2]:
        continue
    if i[1] >= i[0]+i[2]:
        continue
    if i[2] >= i[1]+i[0]:
        continue
    ans += 1

print(ans)


### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-1, 1,-1):
    for j in range(i-1,0,-1):
        x = L[i]-L[j]
        maxindex = bisect.bisect_right(L, x)
        if j>maxindex:
            ans += j-maxindex

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

def main():
    from sys import stdin
    input = stdin.readline
    # 区間更新・一点取得の加法BIT

    class BIT():
        def __init__(self, n):
            self.n = n
            self.maxbit = 2**(len(bin(n))-3)
            self.bit = [0]*(n+1)

        # 初期化する
        def make_bit(self, a):
            n, bit = self.n, self.bit
            for i, j in enumerate(a):
                x, y = i+1, i+2
                while x < n+1:
                    bit[x] += j
                    x += x & (-x)
                while y < n+1:
                    bit[y] -= j
                    y += y & (-y)

        # 区間[i:j]に値vを足す
        def add(self, i, j, v):
            x, y, n, bit = i+1, j+1, self.n, self.bit
            while x < n+1:
                bit[x] += v
                x += x & (-x)
            while y < n+1:
                bit[y] -= v
                y += y & (-y)

        # 位置iの値を出力する
        def output(self, i):
            ret, x, bit = 0, i+1, self.bit
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            return ret

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

    for cnt in range(min(k, 42)):
        ans = []
        bit = BIT(n)
        for i in range(n-1, -1, -1):
            bit.add(max(i-a[i], 0), min(i+a[i]+1, n), 1)
        for i in range(n):
            ans.append(bit.output(i))
        a = ans

    print(*ans)


main()

### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    for cnt in range(min(k, 41)):
        ans = []
        bit = [0]*(n+1)
        for i, j in enumerate(a):
            x, y = max(i-j, 0)+1, min(i+j+1, n)+1
            while x < n+1:
                bit[x] += 1
                x += x & (-x)
            while y < n+1:
                bit[y] -= 1
                y += y & (-y)
        for i in range(n):
            ret, x = 0, i+1
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            ans.append(ret)
        a = ans

    print(*ans)


main()
### BUGGY CODE ###

n = int(input())
l = [i for i in range(1,n+1)]

print(sum(l)-l[-1])


### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

from operator import mul
from functools import reduce

X,Y = map(int,input().split()[:2])

if (X + Y) % 3 != 0:
    print(0)
    exit()

x_tmp=X
y_tmp=Y

x_count=0
y_count=0

while x_tmp*2 != y_tmp:
    x_tmp-=2
    y_tmp-=1
    x_count+=1

y_count = y_tmp//2

sum = x_count + y_count

def cmb(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 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, sum + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ret = cmb(sum,x_count,mod)
print(ret)


### FIXED CODE ###

from operator import mul
from functools import reduce

X,Y = map(int,input().split()[:2])

if (X + Y) % 3 or not (X <= 2*Y and Y <= 2*X):
    print(0)
    exit()

x_tmp=X+1
y_tmp=Y+2

x_count=0
y_count=0

while x_tmp*2 != y_tmp:
    x_tmp-=2
    y_tmp-=1
    x_count+=1

y_count = y_tmp//2 - 1

sum = x_count + y_count

def cmb(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 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, sum + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ret = cmb(sum,x_count,mod)
print(ret)
### BUGGY CODE ###

import math

def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def search_divisor_num_1(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

N = int(input())
ans = 0

for i in range(1,N+1):
    ans += i * search_divisor_num_1(i)

print(ans)

### FIXED CODE ###

N=int(input())
ans = 0
 
for i in range(1, N+1):
    num = N // i
    if num == 1:
        ans += i
    else:
        ans += num * (i + num * i) / 2
 
print(int(ans))
### BUGGY CODE ###

import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    S = list(input())

    a_ord = ord('a')
    z_ord = ord('z')

    set_list = [[] for _ in range(z_ord+1)]
    for i in range(N):
        s = S[i]
        bisect.insort_left(set_list[ord(s)],i)

    Q = int(input())
    for q in range(Q):
        ipt = input().split()
        if ipt[0] == "1":
            i,c = int(ipt[1]), ipt[2]
            j = ord(S[i-1])

            if j == ord(c): continue
            set_list[j].remove(i-1)
            bisect.insort_left(set_list[ord(c)],i-1)
            S[i-1] = c
            # print(set_list[])

        else:
            l,r = int(ipt[1]), int(ipt[2])
            ans = 0
            # if l == r:
            #     print(1)
            #     continue

            for i in range(a_ord,z_ord+1):
                st = set_list[i]
                if not len(st) > 0: continue

                # print(i,set_list[i])
                l_p = bisect.bisect_left(st,l-1)
                r_p = bisect.bisect_right(st,r-1)

                # print(l-1,r-1,l_p,r_p)
                if l_p < r_p:
                    ans += 1

            # print(ans,"____")
            print(ans)



if __name__ == "__main__":
  main()


### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    S = list(input())

    a_ord = ord('a')
    z_ord = ord('z')

    set_list = [[] for _ in range(z_ord+1)]
    for i in range(N):
        s = S[i]
        set_list[ord(s)].append(i)

    Q = int(input())
    for q in range(Q):
        ipt = input().split()
        if ipt[0] == "1":
            i,c = int(ipt[1]), ipt[2]
            j = ord(S[i-1])

            if j == ord(c): continue
            set_list[j].remove(i-1)
            bisect.insort_left(set_list[ord(c)],i-1)
            S[i-1] = c
            # print(set_list[])

        else:
            l,r = int(ipt[1]), int(ipt[2])
            ans = 0
            # if l == r:
            #     print(1)
            #     continue

            for i in range(a_ord,z_ord+1):
                st = set_list[i]
                if not len(st) > 0: continue

                # print(i,set_list[i])
                l_p = bisect.bisect_left(st,l-1)
                r_p = bisect.bisect_right(st,r-1)

                # print(l-1,r-1,l_p,r_p)
                if l_p < r_p:
                    ans += 1

            # print(ans,"____")
            print(ans)



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

def main():
    from itertools import product
    n, s = int(input()), input()
    ans = 0
    rgb = {"R", "G", "B"}
    for c in range(1, n - 1):
        for l in range(0, c):
            for r in range(c + 1, n):
                f = (l - c) != (c - r)
                g = rgb == {s[c], s[r], s[l]}
                if f and g:
                    ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, s = int(input()), input()
    r, g, b = s.count('R'), s.count('G'), s.count('B')
    ans = r * g * b
    v = {'R', 'G', 'B'}
    for i in range(n - 2):
        for j in range(n // 2 + 1):
            if i + j + j < n:
                if v == {s[i], s[i + j], s[i + j + j]}:
                    ans -= 1
    print(ans)


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

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

A.sort(reverse=True)
#print(A)

for i in range(M):
    idx = A.index(max(A))

    A[idx] = int(A[idx] / 2.0)
#    A.sort(reverse=True)

ans = 0
for i in range(N):
    ans += A[i]

print(ans)

### FIXED CODE ###

import heapq

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

for i in range(N):
    A[i] = -A[i]

heapq.heapify(A)

for j in range(M):
    a = heapq.heappop(A)
    b = -1*((-a) // 2)
    heapq.heappush(A,b)

print(-sum(A))
### BUGGY CODE ###

import collections
from scipy.misc import comb
N = int(input())
A = [int(x) for x in input().split()]
C = collections.Counter(A)
def banned_count(seq):
    for i in range(N):
        count = 0
        C[A[i]] -= 1
        for j in C.values():
            count += comb(j, 2, exact=True)
        print(count)
        C[A[i]] += 1
banned_count(A)

### FIXED CODE ###

from collections import Counter
from scipy.misc import comb
N = int(input())
A = input().split()
C = Counter(A)
s = sum([comb(j, 2, exact=True) for j in C.values()])
for i in range(N):
    print(s-C[A[i]]+1)
### BUGGY CODE ###

import numpy as np
from numba import jit
@jit(cache=True)
def solve(n,k,A):
    l,r=0,0
    for ki in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for i,j in enumerate(A):
            l=max(0,i-j)
            r=min(n,i+j+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        np.delete(A,n-1)
    return A

n,k=map(int,input().split())
A=list(map(int,input().split()))
A=np.array(A)
x=solve(n,k,A)
print(*x)

### FIXED CODE ###

import numpy as np
from numba import jit
@jit(cache = True)
def solve(n,k,A):
    l,r=0,0
    for i in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for x,y in enumerate(list(A)):
            l=max(0,x-y)
            r=min(n,x+y+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
X=solve(n,k,A)
print(*X,sep=' ')
### BUGGY CODE ###

s = input()
q = int(input())
lis = []
for _ in range(q):
    i = input()
    if i == '1':
        s = ''.join(list(reversed(s)))
    else:
        a,b,c = i.split()
        if b == '1':
            s = c + s
        else:
            s = s + c
print(s)

### FIXED CODE ###

s = input()
q = int(input())
rev_flag = False
x_lis = []
y_lis = []
for _ in range(q):
    i = input()
    if i == '1':
        rev_flag = not rev_flag
    else:
        a,b,c = i.split()
        if rev_flag:
            if b == '1':
                #s = s + c
                y_lis.append(c)
            else:
                #s = c + s
                x_lis.append(c)
        else:
            if b == '1':
                #s = c + s
                x_lis.append(c)
            else:
                #s = s + c
                y_lis.append(c)
x = ''.join(reversed(x_lis))
y = ''.join(y_lis)
if rev_flag:
    print(''.join(list(reversed(x+s+y))))
else:
    print(x+s+y)
### BUGGY CODE ###

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

count = 0

for a in range(n-2):
    for b in range(a+1,n-1):
        for c in range(b+1,n):
            if arr[a]<arr[b]+arr[c] and arr[b]<arr[c]+arr[a] and arr[c]<arr[a]+arr[b]:
                count +=1

print(count)

### FIXED CODE ###


n = int(input())
arr = list(map(int,input().split()))
arr.sort()

count = 0

for a in range(n-2):
    k = a+2
    for j in range(a+1,n):
        while (k < n and arr[a] + arr[j] > arr[k]):
            k+=1
        
        if k>j:
            count += k-j-1
        
print(count)
### BUGGY CODE ###

N = int(input())
S = input()

def check(l):
    for i in range(N - 2 * l + 1):
        if S.find(S[i : i + l], i + l) > 0:
            return True

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m):
        ok = m
    else:
        ng = m

print(ok)

### FIXED CODE ###

N = int(input())
S = input()

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

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            tmp = 1
            if i > 0:
                tmp += dp[i - 1][j - 1]
            if j - i < tmp:
                continue
            dp[i][j] = tmp
        ans = max(ans, dp[i][j])
print(ans)
### BUGGY CODE ###

n=int(input())
a = [input() for i in range(n)]
b = sorted(list(set(a)))
d = {}
for i in b:
    t = a.count(i)
    d.setdefault(t,[])
    d[t].append(i)

for i in d[max(d.keys())]:
    print(i)


### FIXED CODE ###

from collections import defaultdict

n=int(input())

d=defaultdict(int)


for i in range(n):
    d[input()] +=1

m =max(d.values())

for i,j in sorted(d.items()):
    if j == m :print(i)
### BUGGY CODE ###

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

#sub problem: min cost from 0 to i
memo = []
for i, num in enumerate(H):
  if i == 0:
    memo.append(0)
  elif i == 1:
    memo.append(abs(num - H[i-1]))
  else:
    m = min(abs(num - H[i-j])+ memo[i-j] for j in range(1, K+1) if i - j >= 0)
    memo.append(m)
print(memo[-1])

### FIXED CODE ###

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

#sub problem: min cost from 0 to i
memo = []
for i, num in enumerate(H):
  if i == 0:
    memo.append(0)
  elif i == 1:
    memo.append(abs(num - H[i-1]))
  else:
    m = min(abs(num - H[i-j])+ memo[i-j] for j in range(1, K+1) if i - j >= 0)
    memo.append(m)
print(memo[-1])
### BUGGY CODE ###

N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)

import sys
sys.setrecursionlimit(5000000)


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a


def maxkobai(a, b):
    return a * b // gcd(a, b)


L = maxkobai(N, M)
ret = L
x = ['-' for i in range(L+1)]
#x = ['-'] * (L+1)

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]


for m in range(0, M):
    idx = m * (L // M) + 1
    x_idx = x[idx]
    if x_idx != '-' and x_idx != T[m]:
        ret = -1
        break

print(ret)


### FIXED CODE ###

N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)


S = [ord(c) for c in S]
T = [ord(c) for c in T]


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a


def maxkobai(a, b):
    return a * b // gcd(a, b)


L = maxkobai(N, M)
ret = L
x = dict()

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]


for m in range(0, M):
    idx = m * (L // M) + 1
    tmp = x.get(idx, 0)

    if tmp != T[m] and tmp != 0:
        ret = -1
        break

print(ret)