Harryxun/stf_run huggingface dataset:
"""everything has a cost!"""

from math import *
import random
import functools
import collections
import sys

__author__ = 'p7x'


# sys.stdin = open('in.txt', 'r')
# sys.stdout = open('out.txt', 'w')
# sys.stderr = open('err.txt', 'w')

i, j = 0, 0
n, m = 0, 0


@functools.lru_cache(maxsize=None, typed=False)
def read(ti: int, tj: int) -> int:
    if (ti < n and (tj == m or a[ti] < b[tj])):
        return 1
    elif (tj < m and (ti == n or b[tj] < a[ti])):
        return 2
    elif (ti < n and tj < m and a[ti] == b[tj]):
        return read(ti+1, tj+1)
    else:
        if (ti == i):
            return 3
        else:
            return 1


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

    mins = 0
    while (mins < k):
        v = read(i, j)
        if (v == 1):
            mins += a[i]
            i += 1
        elif (v == 2):
            mins += b[j]
            j += 1
        else:
            break
    if mins > k:
        print(i+j-1)
    else:
        print(i+j)


### FIXED CODE ###

"""everything has a cost!"""

from math import *
import random, functools, collections, sys

__author__ = 'p7x'


# sys.stdin = open('in.txt', 'r')
# sys.stdout = open('out.txt', 'w')
# sys.stderr = open('err.txt', 'w')


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

    for i in range(1,len(a)):
        a[i] += a[i-1]
    for i in range(1,len(b)):
        b[i] += b[i-1]

    j = len(b)-1
    while j > -1 and b[j] > k:
        j -= 1
    ans = j+1
    i = len(a)-1
    while i > -1 and a[i] > k:
        i -= 1
    ans = max(i+1,ans)

    for inx in range(i+1):
        while j > -1 and a[inx] + b[j] > k:
            j -= 1
        ans = max(inx+j+2,ans)
    print(ans)
import bisect

N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
ans = 0
for i in range(N):
  for j in range(i+1, N):
    min_sum = L[i]+L[j]
    more_than = bisect.bisect_left(L[j+1:], min_sum)
    ans += more_than
print(ans)

### FIXED CODE ###

A,B = map(int, input().split())

if A <= 2*B:
  print(int(0))
else:
  print(A-2*B)
import math
instr = intput()
K = int(instr)

COdd = math.ceil(K / 2)
CEven = int(K / 2)

ans = COdd * CEven
print(ans)

### FIXED CODE ###

import math
instr = input()
K = int(instr)

COdd = math.ceil(K / 2)
CEven = int(K / 2)

ans = COdd * CEven
print(ans)
n=int(input())
p = list(map(int, input().split()))
sum = 0
for i in range(1,n):
  if p[i+1]>p[i]>p[i-1] or p[i-1]>p[i]>p[i+1]:
    sum +=1
print(sum)


### FIXED CODE ###

n=int(input())
p = list(map(int, input().split()))
sum = 0
for i in range(1,n-1):
  if p[i+1]>p[i]>p[i-1] or p[i-1]>p[i]>p[i+1]:
    sum +=1
print(sum)
S = input()

# import decimal
import math


odd = []
oddness = []


for i in range(S):
    j = i + 1
    if j % 2 != 0:
        odd.append(j)

# decimal.getcontext().prec = 7
# print(decimal.Decimal(len(odd)) / decimal.Decimal(j))
answer = len(odd) / j

print(round(answer, 7))


### FIXED CODE ###

import sys
import math
N = int(sys.stdin.readline())
# import decimal


odd = []
oddness = []


for i in range(N):
    j = i + 1
    if j % 2 != 0:
        odd.append(j)

# decimal.getcontext().prec = 7
# print(decimal.Decimal(len(odd)) / decimal.Decimal(j))
answer = float(len(odd)) / float(j)
print(answer)
A, B = map(int, input().slit())

A_price = A // 8 * 100

B_price = B // 10 * 100

if A_price == B_price:
  print(A_price)
else:
  print(-1)
  

### FIXED CODE ###

A,B = map(int, input().split())
num = 0
while num < 1011:
  num += 1
  X = num * 0.08
  if int(X) == A:
    Y = num * 0.1
    if int(Y) == B:
      print(num)
      break
    else:
      pass
  elif num == 1010:
    print(-1)
    break
  else:
    pass
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map(int, input().split())
    A = deque([int(input()) for i in range(M)])
    dp = [0]*N
    # 一段目と二段目への行き方
    if len(A) != 0:
        out = A.popleft 
    else:
        out = 0
        
    if out != 1:
        dp[0] = 1
    else:
        dp[0] = 0
        if len(A) != 0:
            out = A.popleft 
    if out != 2:
        dp[1] = 1+dp[0]
    else:
        dp[1] = 0
        if len(A) != 0:
            out = A.popleft 

    for i in range(2,N):
        if i+1 == out:
            dp[i] = 0
            if len(A) != 0:
                out = A.popleft()
        else:
            if dp[i-2] != 0 or dp[i-1] != 0:
                dp[i] = dp[i-2] + dp[i-1]

    if dp[N-1] != 0:
        print(dp[N-1]%(10**9 + 7))
    else:
        print(0)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map(int, input().split())
    A = deque([int(input()) for i in range(M)])
    if N == 1:
        print(1)
    else:
        dp = [0]*N
        # 一段目と二段目への行き方
        if len(A) != 0:
            out = A.popleft() 
        else:
            out = 0

        if out != 1:
            dp[0] = 1
        else:
            dp[0] = 0
            if len(A) != 0:
                out = A.popleft()
        if out != 2:
            dp[1] = 1+dp[0]
        else:
            dp[1] = 0
            if len(A) != 0:
                out = A.popleft()

        for i in range(2,N):
            if i+1 == out:
                dp[i] = 0
                if len(A) != 0:
                    out = A.popleft()
            else:
                if dp[i-2] != 0 or dp[i-1] != 0:
                    dp[i] = dp[i-2] + dp[i-1]

        if dp[N-1] != 0:
            print(dp[N-1]%(10**9 + 7))
        else:
            print(0)
    
if __name__ == '__main__':
    main()
import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = -1, max(Cs)+1, 1
    if func(min_i) or not func(max_i):
        3/0
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
            continue
        index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break


### FIXED CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break
if __name__ == "__main__":
    nset = int(input())

    for i in range(0, nset):
        sa = input()
        sb = input()
        a = int(sa)
        b = int(sb)
        c = a + b

        if len(sa) > 80 or len(sb) > 80 or len(str(c)) > 80:
            print("overflow")
        else:
            print(c)

### FIXED CODE ###

if __name__ == "__main__":
    nset = int(input())

    for i in range(0, nset):
        sa = input()
        sb = input()
        a = int(sa)
        b = int(sb)
        c = a + b

        if len(sa) > 80 or len(sb) > 80 or len(str(c)) > 80:
            print("overflow")
        else:
            print(c)
S = input()
white = 0
total = 0
for i in range len(S):
    if S[i] == "W":
        total += (i - white)
        white += 1
        
print(total)


### FIXED CODE ###

from sys import stdin

S = stdin.readline().rstrip()
#S = input()
white = 0
total = 0
for i in range(len(S)):
    if S[i] == "W":
        total += (i - white)
        white += 1
        
print(total)
a = [input() for i in range(2)]
     
sp = "".join(sorted(list(a[0])))
tmp = list(a[1])
tmp.sort()
tmp.reverse()
tp = "".join(tmp)
     
if sp < tp:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import statistics
import math

a = list(map(int,input().split()))
print( math.ceil(statistics.mean(a)))
order = [int(input()) for i in range(5)]
diff = (sorted(map(lambda x: (x % 10), order)))
diff = [i for i in diff if i != 0]

sum_order = sum(list(map(lambda x: -(-x //10), order)))
print ((sum_order * 10) - 10 + diff[0])


### FIXED CODE ###

order = [int(input()) for i in range(5)]
diff = (sorted(map(lambda x: (x % 10), order)))
diff = [i for i in diff if i != 0]

sum_order = sum(list(map(lambda x: -(-x //10), order))) * 10

if diff != []:
    sum_order += (-10 + diff[0])
    
print (sum_order)
K, S = int(input().split())
ans = 0
for o in range(2, K):
    for p in range(2, K):
        for q in range(2, K):
            if o + p + q == S:
                ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int, input().split())
ans = 0
for o in range(0, K+1):
    for p in range(0, K+1):
            if 0 <= S-o-p <= K:
                ans += 1
print(ans)
def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

dp = [[-1 for col in range(p)] for row in range(n)]

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'

### FIXED CODE ###

def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

dp = [[-1 for col in range(2000)] for row in range(n+1)]

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'
N,K = input().split()
d = input()

print(N-d)

### FIXED CODE ###

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

s = []

for i in range(N):
    s.append(False)
    
for i in range(K):
    d = int(input())
    a = list(map(int,input().split()))
    for j in range(d):
        s[a[j]-1] = True
        
cut = 0
for i in range(N):
    if not s[i]:
        cut += 1

print(cut)
import sys
import numpy as np
from scipy.sparse.csgraph import shortest_path
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = np.zeros((N, N)) #0-indexed
for _ in range(N-1):
    a, b, c = lr()
    graph[a-1, b-1] = c

dist = shortest_path(graph, directed=False).astype(int)
Q, K = lr()
for _ in range(Q):
    x, y = lr()
    print(dist[x-1, K-1] + dist[K-1, y-1])

# 20

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def measure(x):
    dist = [INF] * (N)
    dist[x] = 0
    que = deque()
    que.append(x)
    while que:
        cur = que.popleft()
        cur_dist = dist[cur]
        for next, c in edges[cur]:
            if dist[next] == INF:
                dist[next] = cur_dist + c
                que.append(next)
    
    return dist

N = ir()
INF = 10 ** 15
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = lr()
    edges[a-1].append((b-1, c))
    edges[b-1].append((a-1, c))

Q, K = lr()
dist = measure(K-1)
for _ in range(Q):
    x, y = lr()
    print(dist[x-1] + dist[y-1])


# 20
mountain = [[]] * int(raw_input())
removed = []
while True:
    command = raw_input().split()
    if command[0] == 'push':
        mountain[int(command[1])].append(command[2])
    elif command[0] == 'pop':
        removed.append(mountain[int(command[1])][-1])
        mountain[int(command[1])].pop(-1)
    elif command[0] == move:
        mountain[int(command[2])].append(mountain[int(command[1])][-1])
        mountain[int(command[1])].pop(-1)
    elif command[0] == 'quit':
        break
for block in removed:
    print block

### FIXED CODE ###

mountain = map(lambda x:[], range(int(raw_input())))
removed = []
while True:
    command = raw_input().split()
    if command[0] == 'push':
        mountain[int(command[1]) - 1].append(command[2])
    elif command[0] == 'pop':
        removed.append(mountain[int(command[1]) - 1][-1])
        mountain[int(command[1]) - 1].pop(-1)
    elif command[0] == 'move':
        mountain[int(command[2]) - 1].append(mountain[int(command[1]) - 1][-1])
        mountain[int(command[1]) - 1].pop(-1)
    elif command[0] == 'quit':
        break
for block in removed:
    print block
K, X = map(int, input().split())
ans =[]
for i in range(X - (K-1), X):
    ans.append(i)
for i in range(X, X + (K)):
    ans.append(i)
print(" ".join(map(str, ans)))


### FIXED CODE ###

K, X = map(int, input().split())
ans =[]
for i in range(X - (K-1), X):
    ans.append(i)
for i in range(X, X + (K)):
    ans.append(i)
print(" ".join(map(str, ans)))
n=int(input())
c=[list(map(int,input().split())) for _ in range(n)]
c.sort()
q,w=c[n//2][0],min(c[n//2][1],c[n//2+1][1])
c.sort(key=lambda x: x[1])
e,r=max(c[n//2][0],c[n//2-1][1]),c[n//2][1]
if n%2==0:
    print(max(w-q,r-e)+1)
else:
    print(r-q+1)

### FIXED CODE ###

n=int(input())
a,b=[],[]
for _ in range(n):
    i,j=map(int,input().split())
    a+=[i]
    b+=[j]
a.sort()
b.sort()
c=n//2
if n%2==1:
    print(b[c]-a[c]+1)
else:
    print(b[c]-a[c]+b[c-1]-a[c-1]+1)
n = int(input())

a = []

for i in range(n):
  a.append(int(input())

print('second' if all(a[i] % 2 == 0 for i in range(n)) else 'first')


### FIXED CODE ###

n = int(input())

a = []

for i in range(n):
    a.append(int(input()))

print('second' if all(a[i] % 2 == 0 for i in range(n)) else 'first')
a,b,c,d=map(int,input().split())
e=a+b
f=c+d
if e>f:
  print("Left")
elif e=f:
  print("Balanced")
else:
  print("Right")

### FIXED CODE ###

a,b,c,d=map(int,input().split())
e=a+b
f=c+d
if e>f:
  print("Left")
elif e==f:
  print("Balanced")
else:
  print("Right")
n,w=map(int,input().split())
WV=[]
for i in range(n):
    w,v=map(int,input().split())
    WV.append((w,v))

dp=[0]*(w*2)
for w,v in WV:
    for i in range(w+1):
        try: dp[i]=max(dp[i],dp[i-w]+v)
        except:
            dp[i]=dp[i]


print(max(dp[:w+1]))

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    dd = defaultdict(int)
    dd[0] = 0
    for w, v in items:
        for tw, tv in list(dd.items()):
            if tw + w <= W:
                dd[tw + w] = max(tv + v, dd[tw + w])
    print(max(dd.values()))


if __name__ == "__main__":
    main()
N = int(input())
A = list(map(int,input().split()))
for main_loop in range (0,N):    
    A.sort()
    de = A.count(0)
    del A[:de]
    li = len(A)
    if A[0] == 1:
        break
    for x in range(1,li):
        A[x] = A[x]%A[0]
print(A[0])


### FIXED CODE ###

a,b = map(int,input().split())
if b%a == 0:
    print(a+b)
else:
    print(b-a)
N,M,C = list(map(int,input().split()))
B = list(map(int,input().split()))
total = 0
ans = 0
for i in range(N):
    A = list(map(int,input().split()))
    for j in range(N):
        total += A[i]*B[i]
if total > 0:
    ans += 1
print(ans)

### FIXED CODE ###

N,M,C = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
total = 0
lst = []
for i in range(N):
  A = list(map(int,input().split()))
  for j in range(M):
    total += A[j]*B[j]
  lst.append(total)
  total = 0
for i in lst:
    if i +C > 0:
      ans += 1
print(ans)
import bisect
import heapq 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
a=[que[1]]
l,r=[-que[1]],[que[1]]
heapq.heapify(l)
heapq.heapify(r)
min=0
j=1
tmp=que[1]
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        q1=que[1]
        b+=que[2]
        tmp=-l[0]
        if j%2==0:
            if q1<=-l[0]:
                heapq.heappushpop(l,-q1)
            else:
                heapq.heappushpop(r,q1)

        else:
            if q1<=-l[0]:
                heapq.heappush(r, -heapq.heappushpop(l,-q1))
            else:
                heapq.heappush(l, -heapq.heappushpop(r,q1))
        
        if -l[0]!=r[0]: min+=abs(tmp-q1)
        else: min+=abs(tmp-q1)-abs(-l[0]-tmp)
        tmp=-l[0]

    elif que[0]==2:
        print(tmp,min+b)

### FIXED CODE ###

A,B=map(int,input().split())

if A>12: print(B)
elif A>5: print(B//2)
else: print(0)
import sys
from bisect import *
import math

input = sys.stdin.readline

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

cnum = A.count(0)
amax = max(A)

numind = [[] for i in range(amax+1)]
for i,ai in enumerate(A):
	numind[ai].append(i)

res = 1
for i in range(amax):
	for order, j in enumerate(numind[i+1]):
		res = (res * (bisect(numind[i],j)-order)) % mod

res = (res*math.factorial(3)//math.factorial(3-cnum)) % mod

print(res)

### FIXED CODE ###

import sys
from bisect import *
import math

input = sys.stdin.readline

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

cnum = A.count(0)
amax = max(A)

numind = [[] for i in range(amax+1)]
for i,ai in enumerate(A):
	numind[ai].append(i)

if cnum==0 or cnum>3:
	res = 0
else:
	res = 1
	for i in range(amax):
		if len(numind[i+1])==0 or len(numind[i+1])>3:
			res = 0
			break
		for order, j in enumerate(numind[i+1]):
			res = (res * (bisect(numind[i],j)-order)) % mod

	res = (res*math.factorial(3)//math.factorial(3-cnum)) % mod

print(res)
l = list(map(int, input().split()))
l2 = set(l)
print(l2[0])

### FIXED CODE ###

a,b = map(int, input().split())
if a > b:
  print(a - 1)
else:
  print(a)
import collections
def check(val):
  flag=1
  for v in range(2,int(val**0.5+1)):
    if(val%v==0):
      if(v in x or val//v in x):
        flag=0
        break
  if(flag):
    count+=1
n=int(input())
a=list(map(int,input().split()))
count=0
x=collections.Counter(a)
if(1 in x):
  if(x[1]==1):
    print(1)
  else:
    print(0)
else:
  for each in a:
    if(x[each]==1):
      check(each)
  print(count)
    


### FIXED CODE ###


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

List.sort()
seive=[0]*(List[~0]+1)
count=0
for each in List:
    for i in range(each,List[-1]+1,each):
        seive[i]+=1
        
for each in List:
    if(seive[each]==1):
        count+=1


print(count)
N,Q=map(int,input().split())
S=input()

l=[]
for _ in range(Q):
    l.append(list(map(int,input().split())))

t = [0]*(N+1)
for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
        t[i+1] = 1

for j in range(len(t)):
    print(sum(t[l[j][0]:l[j][1]]))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t = [0]*(N+1)
for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
        t[i+1] = 1

import numpy
res = numpy.cumsum(t)

for _ in range(Q):
    l=list(map(int,input().split()))
    print(res[l[1]-1]-res[l[0]-1])
from sys import stdin

n,k = [int(x) for x in stdin.readline().rstrip().split()]
li = list(map(int,stdin.readline().rstrip().split()))

def score(li,n,k):
    dp = [-1 for _ in li]
    dp[0] = 0
    if n == 1:
        return 0
    elif n <= k:
        return abs(li[-1]-li[0])
    for i in range(1,n):
        dp[i] = min([dp[j] + abs(li[j] - li[i]) for j in range(max(0, i - k), i)])
    return dp[n-1] 

print(score(li,n,k))

### FIXED CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

def score(li,n):
    dp = [-1 for _ in li]
    dp[0] = 0
    dp[1] = abs(li[1]-li[0])
    if n == 1:
        return dp[0]
    elif n == 2:
        return dp[1]
    else:
        for i in range(2,n):
            dp[i] = min(dp[i-2]+abs(li[i]-li[i-2]),dp[i-1]+abs(li[i]-li[i-1]))
        return(dp[n-1])
    
print(score(li,n))
a,b,c=map(int,input().split());print(['NO','YES'][b-a==c-b])A

### FIXED CODE ###

a,b,c=map(int,input().split());print(['NO','YES'][b-a==c-b])
# -*- coding: utf-8 -*-
import itertools
import sys

ships = []
N, M = [int(x) for x in input().split()]
for i in range(M):
    ships.append([int(x) for x in input().split()])

from_1 = set([ship[1] for ship in ships if ship[0] == 1])
to_N = set([ship[0] for ship in ships if ship[1] == N])

if from_1 & to_N:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

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

N = int(input())
print('ABC' + str(N))
def main():
    x, y = map(int, input().split())
    a = list(map(int, input().split()))
    cost = 10*10
    for i in range(n-1):
        cost = min(cost, k - abs(a[i]-a[i+1]))
    print(min(cost, k-abs(a[0]+k-a[n-1])))

if __name__ == "__main__":
    main()

### FIXED CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
ans = a[-1] - a[0]
for i in range(1, n):
    start = a[i]
    end = a[i-1]+k
    ans = min(ans, end-start)
print(ans)
n,k=map(int,input().split())
h=list(map(int,input().split()))
cost=[9999]*n
cost[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i+1):
        cost[i+j]=min(cost[i+j],cost[i]+abs(h[i+j]-h[i]))

print(cost[-1])


### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
cost=[float("inf")]*n
cost[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i)):
        cost[i+j]=min(cost[i+j],cost[i]+abs(h[i+j]-h[i]))

print(cost[-1])
def test(a,s,i):
    if i==len(a) or a[i]>s : return []
    if a[i]==s:return [[i]]
    else: return [[i]+x for x in test(a,s-a[i],i+1)]+test(a,s,i+1)
        

n,s=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
l=test(a,s,0)
out=0
for s in l:
    out+=2**(len(a)-len(s))
print(out)

### FIXED CODE ###

n,s=map(int,input().split()) 
a=list(map(int,input().split()))
d=[[0]*(s+1) for _ in range(n+1)]
d[0][0]=1
for j in range(0,s+1):
    for i in range(1,n+1):
        d[i][j]=2*d[i-1][j]
        if a[i-1]<=j:
            d[i][j]+=d[i-1][j-a[i-1]]
        d[i][j]=d[i][j]%998244353
print(d[n][s])
import copy
import math

inp = str(input())
# inp = "314159265358979323 846264338327950288 419716939 937510582"
inp = inp.split(" ")
a = int(inp[0])
b = int(inp[1])
c = int(inp[2])
d = int(inp[3])

h = c * d / math.gcd(c, d)
e = int(b / c) - int((a-1) / c)
f = int(b / d) - int((a-1) / d)
g = int(b / h) - int((a-1) / h)

print((b-a+1)-(e+f-g))

### FIXED CODE ###

import copy
import fractions

inp = input()
# inp = "314159265358979323 846264338327950288 419716939 937510582"
inp = inp.split(" ")
a = int(inp[0])
b = int(inp[1])
c = int(inp[2])
d = int(inp[3])

h = c * d // fractions.gcd(c, d)
e = int(b // c) - int((a-1) // c)
f = int(b // d) - int((a-1) // d)
g = int(b // h) - int((a-1) // h)

print((b-a+1)-(e+f-g))
s = list(map(int, list(input())))
for i in range(s - 1):
    if s[i] == s[i + 1]:
        print('Bad')
    print('Good')


### FIXED CODE ###

s = list(map(int, list(input())))
for i in range(len(s) - 1):
    if s[i] == s[i + 1]:
        print('Bad')
        break
else:
    print('Good')
N = int(input())
l = list(map(int,input().split()))
count = 1
max = l[0]
for i in range(N):
  if max <= l[i]:
   	count += 1
    max = l[i]
    
print(count)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
max = l[0]
count = 0
for i in range(n):
  if l[i] >= max:
    count += 1
    max = l[i]
    
print(count)
s = input()
t = input()
s.sort()
t.sort(reverse=True)
if s < t:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s = list(input())
t = list(input())
s.sort()
t.sort(reverse=True)
if s < t:
  print('Yes')
else:
  print('No')
H, W = [int(_) for _ in input().split()]
A = [input() for _ in range(N)]
print('#'*(W+2))
for a in A:
    print('#'+a+'#')
print('#'*(W+2))


### FIXED CODE ###

H, W = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
print('#'*(W+2))
for a in A:
    print('#'+a+'#')
print('#'*(W+2))