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

n,k = map(int,raw_input().split())
jis = [map(int, raw_input().split()) for _ in range(k)]
dp = [0 for _ in range(n)]
dp[0] = 1
mod = 998244353
for i in range(1,n):
	for u,v in jis:
		for w in range(u,v+1):
			if i-w>=0:
				dp[i] += dp[i - w]
				dp[i] %= mod
print dp[n-1]

### FIXED CODE ###

n,k = map(int,raw_input().split())
jis = [map(int, raw_input().split()) for _ in range(k)]
jis.sort()

dp = [0 for _ in xrange(n)]
dp[0] = 1
pre = [0 for _ in xrange(n)]
pre[0] = 1
mod = 998244353
for i in range(1,n):
	flag = True
	for u,v in jis:
		uu,vv = i - v, i - u
		
		if vv >= 0:
			dp[i] += pre[vv] - (pre[uu - 1] if uu - 1 >= 0 else 0)
			dp[i] %= mod
	pre[i] += dp[i] + pre[i-1]
	pre[i] %= mod

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

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

count = 0

for i in range(n-1):
    while True:
        if a[i] <= a[i+1]:
            break
        else:
            a[i+1] += 1
            count += 1

print(count)

### FIXED CODE ###

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

count = 0

for i in range(n-1):
    if a[i] > a[i+1]:
        count += (a[i] - a[i+1])
        a[i+1] = a[i]
        
print(count)
### BUGGY CODE ###

import math


def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i + 1)

    left = min(A)
    right = max(A)

    while left < right:
        center = math.floor((left + right) / 2)
        if calc(A, left) <= calc(A, right):
            right = center
        else:
            left = center
    print(calc(A, left))


if __name__ == "__main__":
    main()


### FIXED CODE ###


def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i + 1)

    print(calc(A, sorted(A)[(N)//2]))

#    left = min(A)
#    right = max(A)
#
#    while left < right:
#        c1 = (left + left + right) // 3       # floor
#        c2 = -(-(left + right + right) // 3)  # ceil
#        if calc(A, c1) <= calc(A, c2):
#            right = c2 - 1
#        else:
#            left = c1 + 1
#    print(calc(A, left))


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

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

R, C, K = mapint()
dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
from collections import defaultdict
dic = defaultdict(int)
for _ in range(K):
    r, c, v = mapint()
    dic[(r-1, c-1)] = v

for r in range(R):
    for c in range(C):
        v = dic[(r, c)]
        for i in range(4):
            if c!=0:
                dp[r][c][i] = dp[r][c-1][i]
            if r!=0:
                dp[r][c][0] = max(dp[r][c][0], dp[r-1][c][i])
        for i in range(2, -1, -1):
            dp[r][c][i+1] = max(dp[r][c][i+1], dp[r][c][i]+v)

print(max(dp[R-1][C-1]))

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

R, C, K = mapint()
last_dp = [[0]*4 for _ in range(C)]
dic = [[0]*C for _ in range(R)]
for _ in range(K):
    r, c, v = mapint()
    dic[r-1][c-1] = v

for r in range(R):
    dp = [[0]*4 for _ in range(C)]
    for c in range(C):
        v = dic[r][c]
        for i in range(4):
            if c!=0:
                dp[c][i] = dp[c-1][i]
            if r!=0:
                dp[c][0] = max(dp[c][0], last_dp[c][i])
        if v!=0:
            for i in range(2, -1, -1):
                dp[c][i+1] = max(dp[c][i+1], dp[c][i]+v)
    last_dp = dp

print(max(dp[C-1]))
### BUGGY CODE ###

import math
import copy
# import numpy as np

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

a = getInputListInt()
min = a[0]
max = a[1]

ans_max = 2019
ans = ans_max

for i in range(min, max):
    for j in range(i+1, max+1):
        tmp = (i*j) % ans_max

        if ans > tmp:
            ans = tmp

print(ans)

### FIXED CODE ###

import math
import copy
# import numpy as np

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

a = getInputListInt()
min = a[0]
max = a[1]

ans_max = 2019
ans = ans_max

flg = False

for i in range(min, max):
    for j in range(i+1, max+1):
        tmp = (i*j) % ans_max

        if ans > tmp:
            ans = tmp

        if ans == 0:
            flg = True
            break

    if flg:
        break

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

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None not in ANS[i:i+L//2+1] :
            i += L//2+1
            continue
        if ANS[i] : 
            i += 1
            continue
        else : 
            ANS[i] = min(Whole[i+1-L:i+1])
            i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

N = int(input())
S = input()
def check(l):
  for i in range(N-l):
    s = S[i:i+l]
    if not S.find(s, i+l) < 0:
      return True
  return False
a = 1
b = N
while a < b:
  i = (a + b)//2
  if not check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b-1
print(r)


### FIXED CODE ###

N = int(input())
S = input()
r = 0
i = j = 0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r, j-i)
    j += 1
  else:
    i += 1
print(r)
### BUGGY CODE ###

import math
n = int(input())

for i in range(1, n+1):
  count = 0
  upper = int(math.sqrt(i))
  lower = int(math.sqrt(i/6))
  for x in range(lower, upper):
    for y in range(lower, x+1):
      for z in range(lower, y+1):
        if x*x + y*y + z*z + x*y + y*z + z*x == i:
          if x == y and y == z and z == x:
          	count += 1
          else:
            count += 3
            
  print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

for x in range(1, 100):
  for y in range(1, 100):
    for z in range(1, 100):
      tmp = x*x + y*y + z*z + x*y + y*z + z*x
      if tmp <= n:
        dp[tmp] += 1

for i in range(1, n+1):
  print(dp[i])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    maxHeapify(S, 0)
    return ans
A = [0] * 2000000
n = 0
while True:
    s = readline()
    if s[2] == "s":
        insert(A, int(s[7:]))
    elif s[2] == "t":
        print(extractMax(A))
    else:
        break



### FIXED CODE ###

import sys
from heapq import heapify, heappush, heappop
hq = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        heappush(hq, -int(s[7:]))
    elif s[2] == "t":
        S.append(-heappop(hq))
    else:
        break
print("\n".join(map(str, S)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  n = int(input())
  A = tuple(map(int, input().split()))
  B = tuple(map(int, input().split()))
  def f(n):
    dp = [0]*(n+1)
    for i in range(n+1):
      for a, b in zip(A, B):
        if i-a >= 0:
          dp[i] = max(dp[i], dp[i-a]+b)
    return max(dp[i]+n-i for i in range(n+1))
  m = f(n)
  A, B = B, A
  ans = f(m)
  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
def f(n):
  dp = list(range(n+1))
  for a, b in zip(A, B):
    for i in range(n+1):
      if i-a >= 0:
        dp[i] = max(dp[i], dp[i-a]+b)
  return max(dp)
m = f(n)
A, B = B, A
ans = f(m)
print(ans)
### BUGGY CODE ###

n = int(input())
arr = [int(x) for x in input().split()]
ans = []
for i, x in enumerate(arr):
    temp = 0
    for j, y in enumerate(arr):
        if i != j:
            temp = temp ^ y
    ans.append(temp)
for x in ans:
    print(x, end=" ")


### FIXED CODE ###

n = int(input())
arr = [int(x) for x in input().split()]
ans = []
xor = 0
for i, x in enumerate(arr):
    xor = xor ^ x
for i, x in enumerate(arr):
    temp = xor ^ x

    ans.append(temp)
for x in ans:
    print(x, end=" ")
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
  inp = input()
  if inp[0]=='1':
    S = S[::-1]
  else:
    o, f, c = inp.split()
    if f=='1':
      S = c+S
    else:
      S = S+c
print(S)

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
R = 1
Top = deque()
Top.append(S)
for _ in range(Q):
  inp = input()
  if inp[0]=='1':
    R *= -1
  else:
    o, f, c = inp.split()
    if f=='1' and R==-1 or f=='2' and R==1:
      Top.append(c)
    else:
      Top.appendleft(c)
S = ''.join(Top)
S = S if R==1 else S[::-1]
print(S)
### BUGGY CODE ###

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

for i in range(M):
    a[a.index(max(a))]=max(a)//2
print(sum(a))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
a = [-i for i in list(map(int,input().split()))]
heapq.heapify(a)
for i in range(M):
    m = heapq.heappop(a)
    heapq.heappush(a,-(-m//2))
print(-sum(a))
### BUGGY CODE ###

N = int(input())
A = tuple(map(int, input().split()))

for i in range(1, N+1):
    print(A.count(i))


### FIXED CODE ###

from sys import stdin
import collections

def main():
    readline = stdin.readline
    N = int(input())
    A = list(map(int, readline().split()))
    listN = list(range(1, N+1))    
    c = collections.Counter(A)
    
    for i in listN:
        print(c[i])
main()
### BUGGY CODE ###

n, a = int(input()), sorted(list(map(int, input().split())))
for i in range(int(input())):
    b, c = map(int, input().split())
    for j in range(n):
        if a[j] == b:
            a[j] = c
        if a[j] > c:
            break
    print(sum(a))

### FIXED CODE ###

n, a = int(input()), list(map(int, input().split()))
s = sum(a)
d = [0] * (10 ** 5 + 1)
for i in a:
    d[i] += 1
for i in range(int(input())):
    b, c = map(int, input().split())
    d[c] += d[b]
    s += (c - b) * d[b]
    print(s)
    d[b] = 0
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	r,c,k=MI()
	G=[[0]*(c+1) for _ in range(r+1)]
	dp=[[[0]*5 for i in range(c+1)] for j in range(r+1)]
	for _ in range(k):
		rrr,ccc,v=MI()
		G[rrr][ccc]=v
	#print(G)

	#print(dp)

	for rr in range(1,r+1):
		for cc in range(1,c+1):
			if G[rr][cc]==0:
				dp[rr][cc][1]=dp[rr][cc-1][1]
				dp[rr][cc][2]=dp[rr][cc-1][2]
				dp[rr][cc][3]=dp[rr][cc-1][3]
				dp[rr][cc][4]=max(dp[rr][cc-1][4],dp[rr-1][cc][4])
			else:
				dp[rr][cc][1]=max(dp[rr-1][cc][4]+G[rr][cc],dp[rr][cc-1][1])
				dp[rr][cc][2]=max(dp[rr][cc-1][1]+G[rr][cc],dp[rr][cc-1][2])
				dp[rr][cc][3]=max(dp[rr][cc-1][2]+G[rr][cc],dp[rr][cc-1][3])
				dp[rr][cc][4]=max(dp[rr][cc][1:4])
	#print(dp)
	print(dp[-1][-1][-1])















if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	r,c,k=MI()
	G=[[0]*(c+1) for _ in range(r+1)]
	dp=[[[0]*(c+1) for i in range(r+1)] for j in range(4)]
	for _ in range(k):
		rrr,ccc,v=MI()
		G[rrr][ccc]=v
	#print(G)

	#print(dp)

	for rr in range(1,r+1):
		for cc in range(1,c+1):
			if G[rr][cc]==0:
				for i in range(4):
					dp[i][rr][cc]=max(dp[i][rr][cc-1],dp[3][rr-1][cc])
			else:
				dp[0][rr][cc]=max(dp[3][rr-1][cc],dp[0][rr][cc-1])
				dp[1][rr][cc]=max(dp[0][rr][cc]+G[rr][cc],dp[1][rr][cc-1])
				dp[2][rr][cc]=max(dp[1][rr][cc-1]+G[rr][cc],dp[2][rr][cc-1],dp[1][rr][cc])
				dp[3][rr][cc]=max(dp[2][rr][cc-1]+G[rr][cc],dp[3][rr][cc-1],dp[2][rr][cc])
	#print(dp)
	print(dp[-1][-1][-1])















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

X, Y, A, B, C = map(int, input().split())
p, pi = sorted(list(map(int, input().split())), reverse=True)[:X] + [-1], 0
q, qi = sorted(list(map(int, input().split())), reverse=True)[:Y] + [-1], 0
r, ri = sorted(list(map(int, input().split())), reverse=True) + [-1], 0
ans, nX, nY = 0, 0, 0
while nX < X or nY < Y:
    if r[ri] >= p[pi] and r[ri] >= q[qi]:
        if nX < X and nY < Y:
            if p[pi] >= q[qi]:
                nX += 1
            else:
                nY += 1
        elif nX < X:
            nX += 1
        elif nY < Y:
            nY += 1
        ans += r[ri]
        ri += 1
    elif p[pi] >= q[qi] and p[pi] >= r[ri]:
        if nX < X:
            nX += 1
            ans += p[pi]
            pi += 1
    elif q[qi] >= r[ri] and q[qi] >= p[pi]:
        if nY < Y:
            nY += 1
            ans += q[qi]
            qi += 1

print(ans)


### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())))[-X:]
q = sorted(list(map(int, input().split())))[-Y:]
r = list(map(int, input().split()))
print(sum(sorted(p + q + r)[-(X + Y):]))
### BUGGY CODE ###

n = int(input())
a = 0
b = 0
c = 0
while a < n:
    a+=1
    b=0
    if a == n:
        break
    while a*b-n<0:
        b+=1
        if a*b-n>=0:
            break
        c+=1
print(c)

### FIXED CODE ###

n = int(input())
a = 0
b = 0
c = 0
while a < n:
    a+=1
    if a == n:
        break
    if n%a == 0:
        c+= n//a - 1
    else:
        c+= n//a
print(c)
### BUGGY CODE ###

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
Mod = 10**9+7
n, a, b = map(int, input().split())
N = n+1

def COMinit():
  #N_C_kのN
  for i in range(2, N):
    fac.append(fac[-1]*i%Mod)
    inv.append((-inv[Mod%i] * (Mod//i)) % Mod)
    finv.append(finv[-1] * inv[-1] % Mod)


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

COMinit()
#xのn乗をmで割った余り
def pos(x, n, m):
    if n == 0:
        return 1
    res = pos(x*x%m, n//2, m)
    if n%2 == 1:
        res = res*x%m
    return res


def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

print((power_func(2, n, Mod)-COM(n,a)-COM(n,b)-1)%Mod)

### FIXED CODE ###

def ncr(n, r, p): 
  num = den = 1 
  for i in range(r): 
      num = (num * (n - i)) % p 
      den = (den * (i + 1)) % p 
  return (num * pow(den, p - 2, p)) % p
p=10**9+7
n,a,b = map(int,(input().split()))
bb = ncr(n,a,p)+ncr(n,b,p)+1
print((pow(2,n,p)-(bb%p))%p)
### BUGGY CODE ###

mod = 1000000007
size = 50
f = []
invf = []
def inv(n):
  global mod,size
  if n == 1:
    return 1
  k = [0 for i in range(size)]
  a,b,u = mod,n,size
  for i in range(size):
    k[i],a,b = a//b,b,a%b
    if b == 0:
      u = i
      break
  y0,y1 = 1,-k[0]
  for i in range(1,u):
    y0,y1 = y1,y0-k[i]*y1
  while y1 < 0:
    y1 += mod
  return y1%mod
def comb(n,k):
  global mod,f,invf
  if k < 0 or k > n:
    return 0
  if n == 0 and k == 0:
    return 1
  if n == 0:
    return 0
  return (f[n]*((invf[k]*invf[n-k])%mod))%mod
def init(n):
  global mod,f,invf
  f = [0 for i in range(n+1)]
  invf = [0 for i in range(n+1)]
  f[0],invf[0] = 1,1
  for i in range(1,n+1):
    f[i] = (f[i-1]*i)%mod
    invf[i] = inv(f[i])
  
n,a,b,c = map(int,input().rstrip().split())
init(2*n)
m = 0
for k in range(n):
  m = (m+comb(n+k,n)*(pow(a,n,mod)*pow(b,k,mod)+pow(a,k,mod)*pow(b,n,mod))*inv(pow(100-c,n+k+1,mod)))%mod
print((m*n*100)%mod)

### FIXED CODE ###

mod = 1000000007
size = 50
f = []
invf = []
def inv(n):
  global mod,size
  if n == 1:
    return 1
  k = [0 for i in range(size)]
  a,b,u = mod,n,size
  for i in range(size):
    k[i],a,b = a//b,b,a%b
    if b == 0:
      u = i
      break
  y0,y1 = 1,-k[0]
  for i in range(1,u):
    y0,y1 = y1,y0-k[i]*y1
  while y1 < 0:
    y1 += mod
  return y1%mod
def comb(n,k):
  global mod,f,invf
  if k < 0 or k > n:
    return 0
  if n == 0 and k == 0:
    return 1
  if n == 0:
    return 0
  return (f[n]*((invf[k]*invf[n-k])%mod))%mod
def init(n):
  global mod,f,invf
  f = [0 for i in range(n+1)]
  invf = [0 for i in range(n+1)]
  f[0],invf[0] = 1,1
  for i in range(1,n+1):
    f[i] = (f[i-1]*i)%mod
    invf[i] = inv(f[i])
  
n,a,b,c = map(int,input().rstrip().split())
init(2*n)
m = 0
for k in range(n):
  m = (m+comb(n+k,n)*(pow(a,n,mod)*pow(b,k,mod)+pow(a,k,mod)*pow(b,n,mod))*inv(pow(100-c,n+k+1,mod)))%mod
print((m*n*100)%mod)
### BUGGY CODE ###

# 出現した数のフラグを立てればよいだけでは
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
happend = []
A.sort()
ans = 0

for val in A:
    if count[val] >= 2:
        ans += 1
        happend.append(val)
        continue
    for j in happend:
        if val % j == 0:
            ans += 1
            break
    happend.append(val)

print(N-ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
A.sort()
ans = 0
max_A = max(A)
dp = [True]*(max_A+1)  # 0~max(A)の数についてのリスト
happend = set()
for a in A:
    if C[a] >= 2:
        if a in happend:
            continue
        else:
            # aが存在したという証拠だけは残しておく
            x = a * 2
            while x <= max_A:
                dp[x] = False
                x += a
            happend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a * 2
        while x <= max_A:
            dp[x] = False
            x += a
print(ans)
### BUGGY CODE ###

N = int(input()) + 1
NumberList = list()
for i in range(1,N):
    for j in range(i,N):
        for k in range(j,N):
            NumberList.append([i,j,k])

Answer = 0

def getGCD(abc):
    a = int(abc[2])
    b = int(abc[1])
    c = int(abc[0])
    if a == b and b == c:
        d = 1
    elif a == b or b == c or c == a:
        d = 3
    else:
        d = 6
        
    surplus = b % c
    while surplus != 0:
        b = int(c)
        c = int(surplus)
        surplus = b % c
    surplus = a % c
    while surplus != 0:
        a = int(c)
        c = int(surplus)
        surplus = a % c
    return c * d

for abc in NumberList:
    Answer += getGCD(abc)
print(Answer)


### FIXED CODE ###

N = int(input()) + 1

Answer = 0

def getGCD(a,b,c):
    if a == b and b == c:
        d = 1
    elif a == b or b == c or c == a:
        d = 3
    else:
        d = 6
        
    surplus = a % c
    while surplus != 0:
        a = int(c)
        c = int(surplus)
        surplus = a % c
    surplus = b % c
    while surplus != 0:
        b = int(c)
        c = int(surplus)
        surplus = b % c
    return c * d


for i in range(1,N):
    for j in range(i,N):
        for k in range(j,N):
            Answer += getGCD(k,j,i)
            
print(Answer)
### BUGGY CODE ###

def sol(lis,K):
    import sys
    dp = [sys.maxsize]*len(lis)
    dp[0] = 0
    for i in range(len(lis)):
        for j in range(i+1,i+K+1):
            if j<len(lis):
                dp[j] = min(dp[j],dp[i]+abs(lis[j]-lis[i]))
    print(dp[-1])
n,k = list(map(int,input().split(' ')))
lis = list(map(int,input().split(' ')))
sol(lis,k)

### FIXED CODE ###

def sol(lis,K):
    import sys
    dp = [sys.maxsize]*len(lis)
    dp[0] = 0
    for i in range(len(lis)):
        for j in range(i+1,i+K+1):
            if j<len(lis):
                dp[j] = min(dp[j],dp[i]+abs(lis[j]-lis[i]))
    print(dp[-1])
n,k = list(map(int,input().split(' ')))
lis = list(map(int,input().split(' ')))
sol(lis,k)