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

def resolve():
    n, m = map(int, input().split())

    # i段目に到達するまでのルートの総数
    dp = [1] * (n + 1)

    a = [int(input()) for _ in range(m)]

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

        dp[i] = dp[i - 1]
        if i >= 2:
            dp[i] += dp[i - 2]

    print(dp[n] % (10 ** 9 + 7))
    
resolve()

### FIXED CODE ###

def step(n):
  if n == 0:
      return 1
  steps = [0 for i in range(n + 2)]
  steps[1] = 1
  steps[2] = 2
  for i in range(3, n + 1):
    steps[i] = steps[i - 1] + steps[i - 2]
  return steps[n]

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

a.append(n)

sum = 1

for i in range(m + 1):

  if i == 0:
    sum *= step(a[i] - 1)
    continue
  
  elif i == m:
    sum *= step(a[m] - a[m-1] -1)
    
  elif a[i] - a[i-1] == 1:
    sum = 0
    break

  else:
    sum *= step(a[i] - a[i-1] -2)
    
if m == 0:
  sum = step(n)

print(sum % 1000000007)
### BUGGY CODE ###

#!/usr/local/bin python
# -*- coding: utf-8 -*-
#
# ~/PycharmProjects/atcoder/C-GuessTheNumber.py
#
k, s = map(int, input().split())
pattern = 0

for x in range(min(k+1, s+1)):
    x_tmp = x
    for y in range(min(k+1, s+1-x_tmp)):
        y_tmp = y
        for z in range(min(k+1, s+1-x_tmp-y_tmp)):
            if x_tmp + y_tmp + z == s:
                pattern += 1

print(pattern)

### FIXED CODE ###

#!/usr/local/bin python
# -*- coding: utf-8 -*-
#
# ~/PycharmProjects/atcoder/C-GuessTheNumber.py
#
k, s = map(int, input().split())
pattern = 0

if s == 0 or s == 1:
    print(1)
    exit()

if s <= k:
    print((s+2)*(s+1)//2)
    exit()

# elif 2*k < s <= 3*k:
#     for i in range(k+1):
#         x = k - i
#         y = k
#         z = s - x - y
#         if z <= k:
#             pattern += (y - z + 1)
#         else:
#             break

for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0 <= z <= k:
            pattern += 1


# for x in range(k+1):
#     x_tmp = x
#     for y in range(x_tmp, k+1):
#         y_tmp = y
#         for z in range(y_tmp, s+1-x_tmp-y_tmp):
#             if x_tmp + y_tmp + z == s:
#                 if x_tmp == y_tmp == z:
#                     pattern += 1
#                 elif x_tmp == y_tmp or x_tmp == z or y_tmp == z:
#                     pattern += 3
#                 else:
#                     pattern += 6
#                 break

print(pattern)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [0]*(k+1)
for i in range(k+1):
  for a in A:
    if i-a >= 0:
      dp[i] |= not dp[i-a]
result = dp[k]
if result:
  print("First")
else:
  print("Second")

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [-1]*(k+1)
def dfs(k):
  if dp[k] != -1:
    return dp[k]
  for a in A:
    if k-a >= 0 and dfs(k-a) == 0:
      dp[k] = 1
      return 1
  dp[k] = 0
  return 0
result = dfs(k)
if result:
  print("First")
else:
  print("Second")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    a.count(j)
    print(j)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0
for i in range(n):
  a = l[i]
  for j in range(i + 1, n):
    b = l[j]
    bel1 = 0 #OK
    up1 = n #OUT
    while up1- bel1 > 1:
      mid = (bel1 + up1)//2
      if a + b > l[mid]:
        bel1 = mid
      else:
        up1 = mid
    ans += (bel1-j)
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0
 
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect.bisect_left(l,l[i] + l[j]) - j - 1
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()))

AB = []
for i in range(X):
  for j in range(Y):
    AB.append(A[i] + B[j])
AB.sort(reverse=True)

ans = []
for i in range(min(K, len(AB))):
  for j in range(Z):
    ans.append(AB[i] + C[j])
ans.sort(reverse=True)

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

### 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()))

AB = []
for i in range(X):
  for j in range(Y):
    AB.append(A[i] + B[j])
AB.sort(reverse=True)

ans = []
for i in range(min(K, len(AB))):
  for j in range(Z):
    ans.append(AB[i] + C[j])
ans.sort(reverse=True)

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

N = int(input())

List = []
for i in range(1,10**5):
    for j in range(1,10**5):
        if N == i*j:
            List.append(i+j)

print(min(List)-2)

### FIXED CODE ###

#--------------------------------------------
#ライブラリ等
import sys
import math
from math import sqrt
input = sys.stdin.readline

#---------------------------------------------
N = int(input())
for i in range(int(sqrt(N))+1,-1,-1):
    if N % i == 0:
        print(int(i+(N/i)-2))
        exit()
### BUGGY CODE ###

n, c = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(c)]
C = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n)]

# 全ての色について違和感を記録
dst = [[0, 0, 0] for _ in range(c)]
for ci in range(c):
    for i in range(n):
        for j in range(n):
            c_from = C[i][j]
            dst[ci][(i+j)%3] += D[c_from][ci]

from itertools import permutations
d = 1000*500*500
for p0, p1, p2 in permutations(list(range(c)), 3):
    d = min(d, dst[p0][0] + dst[p1][1] + dst[p2][2])
print(d)


### FIXED CODE ###

n, c = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(c)]
C = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n)]

# 全ての色について違和感を記録
dst = [[0, 0, 0] for _ in range(c)]
for ci in range(c):
    for i in range(n):
        for j in range(n):
            c_from = C[i][j]
            dst[ci][(i+j)%3] += D[c_from][ci]

from itertools import permutations
d = 1000*500*500
for p0, p1, p2 in permutations(list(range(c)), 3):
    d = min(d, dst[p0][0] + dst[p1][1] + dst[p2][2])
print(d)
### BUGGY CODE ###

import numpy as np
inputs = open(0).readlines()

def main(inputs):
    h, w, k = map(int, inputs[0].split())
    cake, count, coords = np.zeros((h, w), dtype=np.int32), 0, {}
    for i, s in enumerate(inputs[1:]):
        for j, c in enumerate(s):
            if c == '#':
                count += 1
                cake[i, j] = count
                coords[count] = (j, i)

    for i in range(1, count+1):
        x, y = coords[i]
        x0, y0 = x-1, y-1
        x1, y1 = x+1, y+1
        while 0 <= x0 and cake[y, x0] == 0:
            cake[y, x0] = i
            x0 -= 1
        x0 += 1
        while x1 < w and cake[y, x1] == 0:
            cake[y, x1] = i
            x1 += 1
        while 0 <= y0 and not np.any(cake[y0, x0:x1]):
            cake[y0, x0:x1] = i
            y0 -= 1
        while y1 < h and not np.any(cake[y1, x0:x1]):
            cake[y1, x0:x1] = i
            y1 += 1

    for rows in cake:
        print(*rows)

main(inputs)

### FIXED CODE ###

import numpy as np
inputs = open(0).readlines()

def main(inputs):
    h, w, k = map(int, inputs[0].split())
    cake, count, coords = np.zeros((h, w), dtype=np.uint), 0, {}
    for i, s in enumerate(inputs[1:]):
        for j, c in enumerate(s):
            if c == '#':
                count += 1
                cake[i, j] = count
                coords[count] = (j, i)
    empty_rows = {i for i, rows in enumerate(cake) if not np.any(rows)}

    for i in range(1, count+1):
        x, y = coords[i]
        x0, y0 = x-1, y-1
        x1, y1 = x+1, y+1
        while 0 <= x0 and cake[y, x0] == 0:
            cake[y, x0] = i
            x0 -= 1
        x0 += 1
        while x1 < w and cake[y, x1] == 0:
            cake[y, x1] = i
            x1 += 1
        while 0 <= y0 and y0 in empty_rows:
            cake[y0, x0:x1] = i
            y0 -= 1
        while y1 < h and y1 in empty_rows:
            cake[y1, x0:x1] = i
            y1 += 1

    for rows in cake:
        print(*rows)

main(inputs)
### BUGGY CODE ###

from collections import deque


H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = ['#' * (W+4)] * 2
for i in range(H):
    S.append('##' + input() + '##')
S.append('#' * (W+4))
S.append('#' * (W+4))

CH += 2
CW += 2
DH += 2
DW += 2

dist = [[-1 for i in range(W + 4)] for j in range(H + 4)]
dist[CH - 1][CW - 1] = 0
q = deque()
q.append([CH, CW])

while len(q) != 0:
    current_pos = q.popleft()
    y = current_pos[0]
    x = current_pos[1]
    if (y, x) == (DH, DW):
        print(dist[DH - 1][DW - 1])
        exit()

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0:
                continue
            next_y = y + i
            next_x = x + j

            if S[next_y - 1][next_x - 1] == '#':
                continue
            if dist[next_y - 1][next_x - 1] == dist[y - 1][x - 1]:
                continue

            if dist[next_y - 1][next_x - 1] == -1 or dist[next_y - 1][next_x - 1] > dist[y - 1][x - 1]:
                if (i == 0 and j in (-1, 1)) or (j == 0 and i in (-1, 1)):
                    q.appendleft([next_y, next_x])
                    dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1]
                else:
                    if dist[next_y - 1][next_x - 1] == -1:
                        q.append([next_y, next_x])
                        dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1] + 1

print(-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())
S = ['#' * (W+4)] * 2
for i in range(H):
    S.append('##' + input() + '##')
S.append('#' * (W+4))
S.append('#' * (W+4))

CH += 2
CW += 2
DH += 2
DW += 2

dist = [[-1 for i in range(W + 4)] for j in range(H + 4)]
dist[CH - 1][CW - 1] = 0
q = deque()
q.append([CH, CW])

while len(q) != 0:
    current_pos = q.popleft()
    y = current_pos[0]
    x = current_pos[1]
    if (y, x) == (DH, DW):
        print(dist[DH - 1][DW - 1])
        exit()

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0:
                continue
            next_y = y + i
            next_x = x + j

            if S[next_y - 1][next_x - 1] == '#':
                continue
            if dist[next_y - 1][next_x - 1] == dist[y - 1][x - 1]:
                continue

            if dist[next_y - 1][next_x - 1] == -1 or dist[next_y - 1][next_x - 1] > dist[y - 1][x - 1]:
                if (i == 0 and j in (-1, 1)) or (j == 0 and i in (-1, 1)):
                    q.appendleft([next_y, next_x])
                    dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1]
                else:
                    if dist[next_y - 1][next_x - 1] == -1:
                        q.append([next_y, next_x])
                        dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1] + 1

print(-1)
### BUGGY CODE ###

# from collections import deque
import numpy as np
from itertools import accumulate
def main():
    n, m, k = map(int, input().split())
    A = np.array([0] + list(map(int, input().split())))
    B = np.array([0] + list(map(int, input().split())))
    X = np.cumsum(A)
    Y = np.cumsum(B)
    P = X[X <= k]
    Q = Y[Y <= k]
    n = len(P)
    m = len(Q)
    # print(P,Q)

    cnt = 0
    # Aをi個、Bをj個選ぶ
    for i in range(n):
        for j in range(m):
            # print(i,j,X[i],Y[j])
            if X[i] + Y[j] <= k:
                cnt = max(cnt, i + j)
    print(cnt)



if __name__ == "__main__":
    main()


### FIXED CODE ###

# from collections import deque
import numpy as np
def main():
    n, m, k = map(int, input().split())
    A = np.array([0] + list(map(int, input().split())))
    B = np.array([0] + list(map(int, input().split())))
    X = np.cumsum(A)
    Y = np.cumsum(B)
    # print(P,Q)

    cnt = 0
    j = m
    # Aをi個、Bをj個選ぶ
    for i, x in enumerate(X):
        if x > k:
            break

        while x + Y[j] > k:
            j -= 1
        cnt = max(cnt, i + j)

    print(cnt)

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

n,m,q=map(int,input().split())
counts=[[0 for _ in range(n)]for _ in range(n)]

for _ in range(m):
    l,r=map(int,input().split())
    for i in range(l):
        for j in range(r-1,n):
            counts[i][j]+=1
for _ in range(q):
    l,r=map(int,input().split())
    print(counts[l-1][r-1])


### FIXED CODE ###

n,m,q=map(int,input().split())
counts=[[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    l,r=map(int,input().split())
    counts[l-1][r-1]+=1
cumsum=[[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        cumsum[i+1][j+1]=cumsum[i+1][j]+counts[i][j]
for j in range(n+1):
    for i in range(n):
        cumsum[i+1][j]+=cumsum[i][j]
        
for _ in range(q):
    l,r=map(int,input().split())
    print(cumsum[r][r]-cumsum[r][l-1]-cumsum[l-1][r]+cumsum[l-1][l-1])
### BUGGY CODE ###

import numpy as np

N, S = map(int, input().split())
A = np.int32(input().split())
M = 998244353

ans = 0
dp = np.zeros((max(S, A.max()) + 1,), dtype=np.int64)
cm = np.zeros_like(dp)
for i, a in enumerate(A):
    dp[:a] = 0
    dp[a] = i + 1
    for s in range(a + 1, S + 1):
        dp[s] = cm[s - a] % M
    cm = (cm + dp) % M
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

### FIXED CODE ###

from sys import stdin

N, S = map(int, stdin.readline().split())
A = list(map(int,stdin.readline().split()))
M = 998244353
V = max(max(A), S)

ans = 0
cs = [0 for _ in range(V + 1)]
for i, a in enumerate(A):
    dp = [0 for _ in range(V + 1)]
    dp[a] = i + 1
    for s in range(a + 1, S + 1):
        dp[s] = cs[s - a]
    cs = [(a + b) % M for a, b in zip(cs, dp)]
    ans = (ans + (N - i) * dp[S]) % M
print(ans)
### BUGGY CODE ###

'''
参考
https://qiita.com/c-yan/items/f7c99c8f8ec418a58c42

棒の全長をL、切断箇所をCとすると、かかるコストは|2C-L|となる
（左端から切断箇所までの長さを2倍し、元の棒の全長を引いたものの絶対値）
∵
・CがL/2よりも左にある場合（=棒の左端からCまでの長さのほうが短い）
⇒Cよりも左側に2C-L足すか、右側を2C-L減らす
・CがL/2よりも右にある場合（=棒の左端からCまでの長さのほうが長い）
⇒Cよりも左側を2C-L減らすか、右側に2C-L足す

与えられたリストAのうち、どの地点をCとするかは
リストAの先頭の要素からN-1個の要素をそれぞれ調べ、
先頭要素から現在の要素までの合計（累積和）を格納するリストを別途作成、
そのリストに対して|2C-L|が最小となるケースを調べる
'''
N = int(input())
A = list(map(int, input().split()))
L = sum(A)
tmp = []

for i in range(N):
    tmp.append(sum(A[:i+1]))

cost = min([abs(c*2-L) for c in tmp])
print(cost)


### FIXED CODE ###

'''
参考
https://qiita.com/c-yan/items/f7c99c8f8ec418a58c42

棒の全長をL、切断箇所をCとすると、かかるコストは|2C-L|となる
（左端から切断箇所までの長さを2倍し、元の棒の全長を引いたものの絶対値）
∵
・CがL/2よりも左にある場合（=棒の左端からCまでの長さのほうが短い）
⇒Cよりも左側に2C-L足すか、右側を2C-L減らす
・CがL/2よりも右にある場合（=棒の左端からCまでの長さのほうが長い）
⇒Cよりも左側を2C-L減らすか、右側に2C-L足す

与えられたリストAのうち、どの地点をCとするかは
リストAの先頭の要素からN-1個の要素をそれぞれ調べ、
先頭要素から現在の要素までの合計（累積和）を格納するリストを別途作成、
そのリストに対して|2C-L|が最小となるケースを調べる
'''
N = int(input())
A = list(map(int, input().split()))
L = sum(A)
#tmp = []
tmp = A[:-1]

for i in range(1, N-1):
#    tmp.append(sum(A[:i+1]))       # 実行時間超過してしまうためコメントアウト
    tmp[i] += tmp[i-1]

cost = min(abs(c*2-L) for c in tmp)
print(cost)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from math import factorial
from itertools import combinations
from collections import Counter
from copy import deepcopy
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under



def main():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n):
        #tmp_a = deepcopy(a)
        #tmp_a[i] = -1
        tmp = a[i]
        a[i] = -1
        tmp_a_c = Counter(a)
        tmp_a_cc = [tmp_a_c[i] for i in tmp_a_c if tmp_a_c[i] > 1]
        r = 0
        for cc in tmp_a_cc:
            r += cmb(cc, 2)
        print(r)
        a[i] = tmp


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

from math import factorial
from itertools import combinations
from collections import Counter
from copy import deepcopy
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_c = Counter(a)
    a_c_sum = 0
    for c in a_c:
        if a_c[c] >= 2:
            a_c_sum += cmb(a_c[c], 2)

    for ea in a:
        if a_c[ea] <= 1:
            sa = 0
        elif a_c[ea] == 2:
            sa = 1
        else:
            sa = cmb(a_c[ea], 2) - cmb(a_c[ea] - 1, 2)
        print(a_c_sum - sa)


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

a = 0
ab = 0
abc = 0
r = 1
 
s = input()
 
for c in s:
    if c == "A":
        a += r
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + r
        r *= 3
 
print(abc % 1000000007)

### FIXED CODE ###

inf = 1000000007
 
a = 0
ab = 0
abc = 0
r = 1
 
s = input()
 
for c in s:
    if c == "A":
        a += r
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = abc * 3 + ab
        ab = ab * 3 + a
        a = a * 3 + r
        r *= 3
        
    a %= inf
    ab %= inf
    abc %= inf
    r %= inf

print(abc)
### BUGGY CODE ###

n=int(input())
wordlist=[input() for i in range(n)]
sortlist=[]
for i in range(n):
    a=list(wordlist[i])
    a.sort()
    a="".join(a)
    sortlist.append(a)
    
count=0
sortlist.sort()


while sortlist:
    a=sortlist.pop()
    times=sortlist.count(a)+1
    for i in range(times-1):
        sortlist.pop()
    b=int(times*(times-1)/2)
    count+=b
    
print(int(count) )   

### FIXED CODE ###

n=int(input())

#単語が全て入ったリストを作るO(n)
wordlist=[input() for i in range(n)]

#wordlistを一つ一つソートさせたものをsortlistとして作るO（n）
sortlist=[]
for i in range(n):
    a=list(wordlist[i])
    a.sort()
    sortlist.append(a)
    
count=0

#ソートリストをソートするO(nlogn)
sortlist.sort()

checkword=""
check=0

for i in range(n): #O(n)
    a=sortlist.pop()
    if checkword==a:
            check+=1
            count+=check
    else:
        check=0
        checkword=a
    
print(int(count) )
### BUGGY CODE ###

from collections import deque


def bfs(G, a, b):
    # グラフGにおいてaからbへの距離
    # 到達不可能な場合は-1を返す
    n = len(G)
    d = [-1] * n
    que = deque([a])
    d[a] = 0
    while que:
        x = que.popleft()
        if x == b:
            return d[b]
        next = G[x]
        for y in next:
            if d[y] == -1:
                que.append(y)
                d[y] = d[x] + 1
    return d[b]


h, w, d = map(int, input().split())
A = [list(map(int, input().split())) for i in range(h)]
G = [[] for k in range(h*w)]
for i in range(h):
    for j in range(w):
        if i > 0:
            G[A[i][j]-1].append(A[i-1][j]-1)
        if i < h-1:
            G[A[i][j]-1].append(A[i+1][j]-1)
        if j > 0:
            G[A[i][j]-1].append(A[i][j-1]-1)
        if j < w-1:
            G[A[i][j]-1].append(A[i][j+1]-1)
D = []
for k in range(h*w):
    if k+d < h*w:
        D.append(bfs(G, k, k+d))

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    x = 0
    for k in range(l-1, r-1, d):
        x += D[k]
    print(x)


### FIXED CODE ###

h, w, d = map(int, input().split())
X = [None for k in range(h*w)]
for i in range(h):
    *A, = map(int, input().split())
    for j in range(w):
        X[A[j]-1] = (i, j)
D = []
for k in range(h*w):
    if k < d:
        D.append(0)
    else:
        x0, y0 = X[k]
        x1, y1 = X[k-d]
        D.append(D[k-d]+abs(x0-x1)+abs(y0-y1))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(D[r-1]-D[l-1])
### BUGGY CODE ###

n = int(input())
string = [input() for i in range(n)]
string2 = [''.join(sorted(x)) for x in string]
count = 0
for i in range(n-1):
    for j in range(i+1, n):
        if string2[i] == string2[j]:
            count += 1

print(count)
#print(string2)


### FIXED CODE ###

import math
def combo(a):
    return (math.factorial(a))/(math.factorial(a-2)*2)

from collections import Counter
n = int(input())
count = 0
string = [input() for i in range(n)]
string2 = [''.join(sorted(x)) for x in string]

'''for i in range(n-1):
    for j in range(i+1, n):
        if string2[i] == string2[j]:
            count += 1'''
li = Counter(string2)
li1=[[key,value] for key, value in li.items()]
for i in range(len(li1)):
    if li1[i][1] == 1:
        li1[i][1] = 0
for i in range(len(li1)):
    if li1[i][1] != 0:
        li1[i][1] = combo(li1[i][1])
for i in range(len(li1)):
    count += li1[i][1]
print(int(count))
### BUGGY CODE ###

N = int(input())
S = input()
c = 0
for i in range(N):
    for j in range(i, N):
        for k in range(j, N):
            if len(set([S[i], S[j], S[k]])) == 3 and j - i != k - j:
                c += 1
print(c)


### FIXED CODE ###

N = int(input())
S = input()
a = S.count("R") * S.count("G") * S.count("B")
c = 0
for i in range(N):
    for j in range(i + 1, N):
        k = 2 * j - i
        if k >= N:
            continue
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            c += 1
print(a - c)
### BUGGY CODE ###

n = int(input())
ps = input().split()
m = 1
fps = []
for i in range(1, n):
  fps.append(int(ps[i-1]))
  if min(fps) > int(ps[i]):
    m += 1
print(m)

### FIXED CODE ###

n = int(input())
ps = list(map(int, input().split()))
fps = [ps[0]]
for i in range(1,n):
  if fps[len(fps)-1] > ps[i]:
    fps.append(ps[i])
print(len(fps))
### BUGGY CODE ###

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

import numpy as np

EDPC = "https://atcoder.jp/contests/dp/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

################ DANGER ################
test = ""
#test = \
"""
5 3
10 30 40 50 20
ans 30
0 20 30 40 30
"""

"""
3 1
10 20 10
ans 20
"""

"""
2 100
10 10
ans 0
"""

"""
10 4
40 10 20 70 80 10 20 70 80 60
ans 40
0 30 20 30 40 30 20 30 40 40
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  

n, k = map(int, input2().split())
a = list(map(int, input2().split()))
k = min(n-1, k)

def main(n, k, a):
    aa = np.concatenate([a])
    dp = np.concatenate([np.abs(aa - aa[0])[:k+1], 
                                np.zeros(n-k-1, dtype="int")])
    for i in range(k+1, n):
        dp[i] = min(dp[j] + abs(a[i] - a[j]) for j in range(i-k, i))
        dp[i] = np.min(dp[i-k:i+1] + np.abs(aa[i-k:i+1] - aa[i]))
    
    return dp[-1]


if __name__ == "__main__":
    print(main(n, k, a))


### FIXED CODE ###

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

import numpy as np

EDPC = "https://atcoder.jp/contests/dp/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

################ DANGER ################
test = ""
#test = \
"""
5 3
10 30 40 50 20
ans 30
0 20 30 40 30
"""

"""
3 1
10 20 10
ans 20
"""

"""
2 100
10 10
ans 0
"""

"""
10 4
40 10 20 70 80 10 20 70 80 60
ans 40
0 30 20 30 40 30 20 30 40 40
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  

n, k = map(int, input2().split())
a = list(map(int, input2().split()))
k = min(n-1, k)

def main(n, k, a):
    aa = np.concatenate([a])
    dp = np.concatenate([np.abs(aa - aa[0])[:k+1], 
                                np.zeros(n-k-1, dtype="int")])
    for i in range(k+1, n):
        dp[i] = np.min(dp[i-k:i] + np.abs(aa[i-k:i] - aa[i]))
    
    return dp[-1]


if __name__ == "__main__":
    print(main(n, k, a))