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

def main():
    from bisect import bisect_left as bs
    n, m, *abc = map(int, open(0).read().split())
    a = sorted(abc[:n])
    *bc, = zip(*[iter(abc[n:])] * 2)
    bc = sorted(bc, key=lambda x: x[1], reverse=True)

    ans = 0
    for b, c in bc:
        i = bs(a, c)
        if i == 0:
            break
        j = min(i, b)
        ans += j * c
        a = a[j:]

    print(ans + sum(a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    n, m, *abc = map(int, open(0).read().split())
    a = Counter(abc[:n])
    bc = abc[n:]
    for i, j in zip(*[iter(bc)] * 2):
        a[j] += i

    cnt = n
    ans = 0
    keys = list(a.keys())
    keys.sort(reverse=True)

    for k in keys:
        m = a[k]
        if m <= cnt:
            ans += k * m
            cnt -= m
        else:
            ans += k * cnt
            break

    print(ans)


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

import sys
input = sys.stdin.readline

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

l = [0] * 100000
m = list(range(1,100001))

for i in range(n):
  l[a[i]-1] += 1
  
for j in range(q):
  l[b[j][1]-1] += l[b[j][0]-1]
  l[b[j][0]-1] = 0
  print(sum(list(map(lambda x,y: x*y, l, m))))

### FIXED CODE ###

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

l = [0] * 100001

for i in a:
  l[i] += 1
  
for j in range(q):
  b, c = map(int,input().split())
  l[c] += l[b]
  ans += l[b] * (c-b)
  l[b] = 0
  print(ans)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    P = [x - 1 for x in P]
    C = list(map(int, input().split()))
    ans = -(10 ** 18)
    for i in range(N):
        j = i
        S = 0
        L = 0
        for _ in range(K):
            j = P[j]
            S += C[j]
            L += 1
            ans = max(ans, S)
            if j == i:
                break
        if j == i:
            M = max(0, K // L - 1)
            T = S * M
            for _ in range(M * L, K):
                j = P[j]
                T += C[j]
                ans = max(ans, T)
    print(ans)


if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    P = [x - 1 for x in P]
    C = list(map(int, input().split()))
    ans = -(10 ** 18)
    for i in range(N):
        j = i
        S = 0
        L = 0
        for _ in range(K):
            j = P[j]
            S += C[j]
            L += 1
            ans = max(ans, S)
            if j == i:
                break
        if j == i:
            M = max(0, K // L - 1)
            T = S * M
            for _ in range(M * L, K):
                j = P[j]
                T += C[j]
                ans = max(ans, T)
    print(ans)


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

import sys
from collections import deque


def bfs(links, s, limit):
    not_reachable = (1 << len(links)) - 1
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        if cost > limit:
            break
        not_reachable ^= 1 << v
        cost += 1
        q.extend((cost, u, v) for u in links[v] if u != p)
    return not_reachable


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    link_list = []
    for a, b in zip(ab[0::2], ab[1::2]):
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)
        link_list.append((a, b))

    limit = k // 2
    if k % 2 == 0:
        ans = min(bin(bfs(links, v, limit)).count('1') for v in range(n))
    else:
        dists = [bfs(links, v, limit) for v in range(n)]
        ans = min(bin(dists[a] & dists[b]).count('1') for a, b in link_list)
    return ans


n, k, *ab = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, ab))


### FIXED CODE ###

import sys
from collections import deque


def bfs(links, s, limit):
    not_reachable = [True] * len(links)
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        if cost > limit:
            break
        not_reachable[v] = False
        cost += 1
        q.extend((cost, u, v) for u in links[v] if u != p)
    return not_reachable


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    for a, b in zip(ab[0::2], ab[1::2]):
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)

    ans = n
    thr = k // 2
    if k % 2 == 0:
        ans = min(sum(bfs(links, v, thr)) for v in range(n))
    else:
        dists = [bfs(links, v, thr) for v in range(n)]
        for a, b in zip(ab[0::2], ab[1::2]):
            a -= 1
            b -= 1
            ans = min(ans, sum(d1 and d2 for d1, d2 in zip(dists[a], dists[b])))
    return ans


n, k, *ab = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, ab))
### BUGGY CODE ###

n=int(input())
s=list(input())

l=[]
for i in range(n):
    x = s[:i].count('W') + s[i:].count('E')
    l.append(x)
    x=0

print(min(l))

### FIXED CODE ###

n=int(input())
s=list(input())
t=list(reversed(s))
#print(s,t)

S,T=[],[]
x,y=0,0
for i in range(n):
    if s[i]=='W':
        x+=1
        S.append(x)
    else:
        S.append(x)
    
    if t[i]=='E':
        y+=1
        T.append(y)
    else:
        T.append(y)

S=[0]+S
T=[0]+T

T.reverse()
#print(S,T)

z=3*(10**5)
for j in range(n):
    z=min(z,S[j]+T[j+1])
    #print(S[j],T[j+1])

print(z)
### BUGGY CODE ###

import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0

    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

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

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

n = int(input())
if n==1:
    print(0)
elif is_prime(n):
    print(1)
else:
    cnt = 0
    for i in range(2, n):
        if is_prime(i):
            c = 1
            while n%pow(i,c)==0:
                n /= pow(i,c)
                cnt += 1
                c += 1
        if n < i:
            break
    print(cnt)

### FIXED CODE ###

import math
def fac(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

n = int(input())
if n==1:
    print(0)
elif is_prime(n):
    print(1)
else:
    cnt = 0
    P = fac(n)
    for p,_ in P:
        c = 1
        while n%pow(p,c)==0:
            n /= pow(p,c)
            cnt += 1
            c += 1
    print(cnt)
### BUGGY CODE ###

#! /usr/bin/env python3
def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    G = []
    for i in range(H):
        G += [[[0,1][x=='#']for x in input()]]

    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]
    
    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    
    s = [[0] * W for x in range(H)]
    
    while f:
        f = False
        while q:
            t = []
            for y, x in q:
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        for y, x in a:
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and s[py][px] == 0:
                    s[py][px] == 1
                    b += [(py, px)]
                    q += [(py, px)]
        # for i in G:
        #     print(i)
        # print()
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

main()



### FIXED CODE ###

#! /usr/bin/env python3
def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    G = []
    for i in range(H):
        G += [[[0,1][x=='#']for x in input()]]

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


    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    while f:
        f = False
        while q:
            t = []
            for y, x in q:
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        s = set()
        for y, x in a:
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and (py,px) not in s:
                    s.add((py,px))
                    b += [(py, px)]
                    q += [(py, px)]
        # for i in G:
        #     print(i)
        # print()
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

main()
### BUGGY CODE ###

import math

X = int(input())
X_sqrt = int(math.sqrt(X))

flag = 0
while flag == 0:
  if X >= 10**5 + 3:
    print("big")
    break
    
  flag = 1
  for i in range(2, X_sqrt):
    if X % i == 0:
      flag = 0
      break
  
  if flag == 1:
    print(X)
    break

### FIXED CODE ###

import math

X = int(input())

flag = 1
while True:
  i = 2
  flag = 1
  while i * i <=  X:
    if X % i == 0:
      flag = 0
      break
    i += 1
  
  if flag == 1:
    print(X)
    break
    
  X += 1
### BUGGY CODE ###

def main():
    n = int(input())
    a = list()
    for i in range(n):
        m = input()
        if m in a:
            a.remove(m)
        else:
            a.append(m)
    print(len(a))


if __name__ == "__main__":
    main()


### FIXED CODE ###

N = int(input())
nums = {}
for i in range(N):
    n = int(input())
    if n in nums.keys():
        nums[n] += 1
    else:
        nums[n]=1
c = 0
for te in nums.values():
   if te % 2 == 1:
       c+=1
print(c)
### BUGGY CODE ###

H,W=map(int,input().split())
S=[]
for h in range(H):
    Sh=list(input())
    newSh=[]
    for w in range(W):
        if Sh[w]=='#':
            newSh.append(1)
        else:
            newSh.append(0)
    Sh=newSh
    S.append(Sh)
    
L=[]
for h in range(H):
    Lh=[]
    a=0
    for w in range(W):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Lh=Lh+[a]
    L.append(Lh)

R=[]
for h in range(H):
    Rh=[]
    a=0
    for w in range(W):
        if S[h][-(1+w)]==0:
            a+=1
        else:
            a=0
        Rh=[a]+Rh
    R.append(Rh)

U=[]
for w in range(W):
    Uw=[]
    a=0
    for h in range(H):
        if S[h][w]==0:
            a+=1
        else:
            a=0
        Uw=Uw+[a]
    U.append(Uw)
U=[[U[w][h] for w in range(W)] for h in range(H)]
    
D=[]
for w in range(W):
    Dw=[]
    a=0
    for h in range(H):
        if S[-(1+h)][w]==0:
            a+=1
        else:
            a=0
        Dw=[a]+Dw
    D.append(Dw)
D=[[D[w][h] for w in range(W)] for h in range(H)]

maxScore=0
for h in range(H):
    for w in range(W):
        score=L[h][w]+R[h][w]+U[h][w]+D[h][w]-3
        if score>maxScore:
            maxScore=score
print(maxScore)

### FIXED CODE ###

import numpy as np
H,W=map(int,input().split())
S=[list(input()) for h in range(H)]
S=[[1 if s=='.' else 0 for s in S[h]] for h in range(H)]
S=np.array(S)
L=S.copy()
R=S.copy()
U=S.copy()
D=S.copy()
for w in range(1,W):
    L[:,w]=(L[:,w-1]+1)*S[:,w]
    R[:,-(1+w)]=(R[:,-w]+1)*S[:,-(1+w)]
for h in range(1,H):
    U[h,:]=(U[h-1,:]+1)*S[h,:]
    D[-(1+h),:]=(D[-h,:]+1)*S[-(1+h),:]
print(int((L+R+U+D).max())-3)
### BUGGY CODE ###

def main():
    from sys import stdin
    n = int(stdin.readline().rstrip())
    s = list(map(int,list(stdin.readline().rstrip())))
    ans=0
    for i in range(1000):
        tap = (i//100,(i//10)%10,i%10)
        flag = 0
        for p in s:
            if flag == 0:
                if p==tap[0]:
                    flag = 1
            elif flag == 1:
                if p==tap[1]:
                    flag = 2
            elif flag == 2:
                if p==tap[2]:
                    flag = 0
                    ans+=1
                    break
    
    print(ans)
main()

### FIXED CODE ###

def main():
    from sys import stdin
    n = int(stdin.readline().rstrip())
    s = list(map(int,list(stdin.readline().rstrip())))
    ans=0
    g = set(list(range(10))) - set(s)
    for i in range(1000):
        tap = (i//100,(i//10)%10,i%10)
        if set(tap) & g == set({}):
            flag = 0
            for p in s:
                if flag == 0:
                    if p==tap[0]:
                        flag = 1
                elif flag == 1:
                    if p==tap[1]:
                        flag = 2
                elif flag == 2:
                    if p==tap[2]:
                        flag = 0
                        ans+=1
                        break
        else:
            continue

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

N = input()
count=0
for i in range(len(N)+1):
  for j in range(i+1,len(N)+1):
    if(int(N[i:j])%3!=0):
      continue
    if(int(N[i:j])%673==0):
      count+=1

print(count)


### FIXED CODE ###

from collections import Counter
N = input()
S=0
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S = int(X)*pow(10,i,2019) % 2019
  S=mod_count[i]+S
  mod_count.append(S%2019)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))
### BUGGY CODE ###

n=int(input())
P=list(map(int,input().split()))
Q=[]
ans = 0
for i in range(n):
  Q.append(P[i])
  if P[i] == min(Q):
    ans += 1
print(ans)

### FIXED CODE ###

n=int(input())
P=list(map(int,input().split()))
x=float("inf")
ans = 0
for i in range(n):
  if x > P[i]:
    ans += 1
    x = P[i]
print(ans)
### BUGGY CODE ###

X = list(map(int, input().split()))
N = X[0]
K = X[1]
if K == 1:
  print(0)
else:  
  while True:
    A = abs(N - K)
    if N > A:
      N = A
    else:
      break
  print(N)

### FIXED CODE ###

X = list(map(int, input().split()))
N = X[0]
K = X[1]
t = N % K
s = K - t
if t <= s:
  print(t)
else:
  print(s)
### BUGGY CODE ###

N = int(input())

s = 0
for i in range(N):
    s += i

print(s)

### FIXED CODE ###

N = int(input())

s = N * (N - 1) // 2

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

r, g, b, n = map(int,input().split())
ans = 0

for i in range(n+1):
    if (i*r) > n:
        continue
    for j in range(n+1):
        if (i*r) + (j*g) > n:
            break
        if n-(i*r)-(j*g) >= 0 and (n-(i*r)-(j*g))%b == 0:
            ans += 1

print(ans)


### FIXED CODE ###

r,g,b,n=map(int, input().split())

sum=0

for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        if (n-i*r-j*g)%b==0:
            sum=sum+1
        #    print(i*r,j*g,(n-(i*r)-(j*g))%b)

print(sum)
### BUGGY CODE ###

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

mod = 10**9 + 7
at = [a[i] % mod for i in range(n)]

ans = 0
for i in range(n):
  ans += (sum(at[i+1:]) % mod) *at[i]
print(ans % mod)

### FIXED CODE ###

n = int(input())
a = tuple(map(int,input().split()))
t = 0
mod = 10**9 + 7
at = []
for j in range(1,n):
  t += a[n-j] % mod 
  at.append(t)

ans = 0
for i in range(n-1):
  ans += at[n-2-i] *a[i]
print(ans % mod)
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
L.sort()
ans=0
for n in range(1,N):
  b=L[n]
  for k in range(n):
    a=L[k]
    left=n+1
    right=N
    while left<right:
      mid=(left+right)//2
      if L[mid-1]<a+b<=L[mid]:
        ans+=(mid-n-1)
        break
      elif a+b<L[mid]:
        right=mid
      else:
        left=mid+1
    ans+=(left-n-1)
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
L=list(map(int,input().split()))
L.sort()
ans=0
for n in range(1,N):
  b=L[n]
  for k in range(n):
    a=L[k]
    index=bisect.bisect_left(L,a+b)
    ans+=(index-n-1)
print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=[0]*(n-1)
    b=[0]*(n-1)
    for i in range(n-1):
        a[i],b[i] = map(int,input().split())
    import collections
    k=collections.Counter(a+b).most_common()[0][1]
    color_list=list(range(k))
    
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        tree[a[i]-1].append(b[i])
        tree[b[i]-1].append(a[i])
        
    used_colors=[[] for _ in range(n)]
    ans=dict()
    q = [(1,0)]
    while q:
        x,parent = q.pop()
    #    if not x in checked:        checked.append(x)
        if parent!=0:
            for i in color_list:
                if not i in used_colors[parent-1]:
                    current_color=i
                    break
            used_colors[parent-1].append(current_color)
            used_colors[x-1].append(current_color)
        
            ans[str(parent)+"_"+str(x)]=current_color
        for y in tree[x-1]:
            if y == parent:
                continue
            q.append((y,x))
    
    print(k)
    for i in range(n-1):
        s=str(a[i])+"_"+str(b[i])
        print(ans[s]+1)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n=int(input())
    a=[0]*(n-1)
    b=[0]*(n-1)
    for i in range(n-1):
        a[i],b[i] = map(int,input().split())
    import collections
    k=collections.Counter(a+b).most_common()[0][1]
    color_list=list(range(k))
    
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        tree[a[i]-1].append(b[i])
        
    q = collections.deque([(0,1,0)])#親、子、色
    ans=dict()
    while q:
        parent,togo,old_color = q.popleft()
    #    print(parent,togo,old_color)
        col=1
        for togotogo in tree[togo-1]:
    #        print(togotogo)
            if togotogo == parent:
                continue
            if col == old_color:
                col+=1
            q.append((togo,togotogo,col))
            ans["_".join(map(str,(togo,togotogo)))]=col
            col+=1
        
    print(k)
    for i in range(n-1):
        s=str(a[i])+"_"+str(b[i])
        print(ans[s])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import defaultdict

mod = 10 ** 9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]
dp = [0] * (N + 1)
dp[0] = 1

for i in range(1, N):
    if C[i] == C[i - 1]:
        dp[i] = dp[i - 1]
    else:
        max_k = -1
        for k in range(i - 1):
            if C[k] == C[i]:
                max_k = max(max_k, k)
        if max_k == -1:
            dp[i] = dp[i - 1]
        else:
            dp[i] = dp[i - 1] + dp[max_k]

print(dp[N - 1])

### FIXED CODE ###

# 解説 https://betrue12.hateblo.jp/entry/2019/03/17/011847
# from collections import defaultdict

mod = 10 ** 9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]
# L = [-1] * (N + 10)  # 出たところ
# dp = [-1] * (N + 10)
# dp[0] = 1
L  = [-1] * (2*10**5 + 10)
dp = [-1] * (2*10**5 + 10)
dp[0] = 1
 

for i in range(N):
    if L[C[i]] == -1:
        dp[i + 1] = dp[i]
    elif C[i] == C[i - 1]:
        dp[i + 1] = dp[i]
    else:
        dp[i + 1] = dp[i] + dp[L[C[i]]]
    
    dp[i + 1] %= mod
    L[C[i]] = i + 1

print(dp[N])
### BUGGY CODE ###

import bisect
N , M = map(int,input().split())
A = [int(i) for i in input().split()]
A.sort()
for _ in range(M):
    a = A.pop(-1)//2
    A.insert(bisect.bisect_left(A,a),a)
print(sum(A))


### FIXED CODE ###

import heapq

N , M = map(int,input().split())
A = [-int(i) for i in input().split()]
heapq.heapify(A)
for _ in range(M):
    a = -heapq.heappop(A) >> 1
    heapq.heappush(A,-a)
print(-sum(A))
### BUGGY CODE ###

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

mod = 10**9+7

num_way = [0] * (n+1)
num_way[0] = 1
if 1 in broken:
	num_way[1] = 0
else:
	num_way[1] = 1

for i in range(2, (n+1)):
	if i in broken:
		num_way[i] = 0
	else:
		num_way[i] = (num_way[i-1] + num_way[i-2]) % mod

print (num_way[n])

### FIXED CODE ###

n, m = list(map(int, input().split() ))
broken = [int(input()) for _ in range(m)]
broken.append(-1) #番兵
broken_idx = 0

mod = 10**9+7

num_way = [0] * (n+1)
num_way[0] = 1
if broken[broken_idx] == 1:
	num_way[1] = 0
	broken_idx += 1
else:
	num_way[1] = 1

for i in range(2, (n+1)):
	if broken[broken_idx] == i:
		num_way[i] = 0
		broken_idx += 1
	else:
		num_way[i] = (num_way[i-1] + num_way[i-2]) % mod

print (num_way[n])
### BUGGY CODE ###

import sys
def input():return sys.stdin.readline()
n,k=[int(i) for i in input().split()]
h=[int(i) for i in input().split()]
dp=[float('inf')]*n
dp[0]=0
for i in range(1,n):
	dp[i]=min([dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i)])
print(dp[-1])

### FIXED CODE ###

def flog2():
	import sys
	def input():return sys.stdin.readline()
	n,k=[int(i) for i in input().split()]
	h=[int(i) for i in input().split()]
	dp=[float('inf')]*n
	dp[0]=0
	for i in range(1,n):
		dp[i]=min([dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i)])
	print(dp[-1])
	
if __name__ == "__main__":
	flog2()
### BUGGY CODE ###

n, m = map(int, input().split())
ls = []
rs = []
for i in range(m):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
n_all = 0
for card in range(1,n+1):
    auth = True
    for gate in range(m):
        if not ls[gate] <= card <= rs[gate]:
            auth = False
    if auth == True:
        n_all += 1
print(n_all)

### FIXED CODE ###

n, m = map(int, input().split())
ls = []
rs = []
for i in range(m):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
n_all = min(rs) - max(ls) + 1
if n_all < 0: n_all =0
print(n_all)
### BUGGY CODE ###

import numpy as np
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
s = [[a%10,a//10*10+10,a],[b%10,b//10*10+10,b],[c%10,c//10*10+10,c],[d%10,d//10*10+10,d],[e%10,e//10*10+10,e]]
s.sort()
while True:
    if s[0][0] == 0:
        s[0][1]-=10
        s.append(s.pop(0))
    else:
        break
s = np.array(s)
ans = s[0][2] + sum(s[1:,1])
print(ans)

### FIXED CODE ###

import numpy as np
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
s = [[a%10,a//10*10+10,a],[b%10,b//10*10+10,b],[c%10,c//10*10+10,c],[d%10,d//10*10+10,d],[e%10,e//10*10+10,e]]
s.sort()
for i in range(5):
    if s[0][0] == 0:
        s[0][1]-=10
        s.append(s.pop(0))
    else:
        break
s = np.array(s)
ans = s[0][2] + sum(s[1:,1])
print(ans)
### BUGGY CODE ###

N = int(input())
print(0, flush=True)
tmp = input()
if tmp == 'Vacant':
    exit()
print(N - 1, flush=True)
tmp = input()
if tmp == 'Vacant':
    exit()

### FIXED CODE ###

N = int(input())
print(0, flush=True)
l = input()
if l == 'Vacant':
    exit()
print(N - 1, flush=True)
t = input()
if t == 'Vacant':
    exit()

top = N - 1
lo = 0
while True:
    mid = (top + lo) // 2
    print(mid, flush=True)
    tmp = input()
    if tmp == 'Vacant':
        exit()
    elif ((mid - lo) % 2 != 0 and l == tmp) or ((mid - lo) % 2 == 0 and l != tmp):
        top = mid
    else:
        lo = mid
        l = tmp