Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
S=input()

if N==1:
    print(1)
    exit()

L=[]
if S[0]=='0':
    L.append(0)
    cur=start=0
else:
    cur=start=1
cnt=0
for i in range(N):
    if cur==0:
        if S[i]=='0':
            cnt+=1
        else:
            L.append(cnt)
            cnt=1
            cur=1
    else:
        if S[i]=='1':
            cnt+=1
        else:
            L.append(cnt)
            cnt=1
            cur=0
else:
    if cnt!=0:
        if cur==0:
            L.append(cnt)
        else:
            L.append(cnt)
if S[-1]=='0':
    L.append(0)

acc=[0]+list(accumulate(L))
acc+=[0]*10000
mx=0
for i in range(0, len(L), 2):
    mx=max(mx, acc[i+(K*2+1)]-acc[i])

print(mx)


### FIXED CODE ###

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

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
S=input()

if N==1:
    print(1)
    exit()

L=[]
cnt0=0
if S[0]=='0':
    L.append(0)
    cur=0
else:
    cur=1
cnt=0
for i in range(N):
    if cur==0:
        if S[i]=='0':
            cnt+=1
        else:
            L.append(cnt)
            cnt=1
            cur=1
            cnt0+=1
    else:
        if S[i]=='1':
            cnt+=1
        else:
            L.append(cnt)
            cnt=1
            cur=0
else:
    if cnt!=0:
        if cur==0:
            L.append(cnt)
            cnt0+=1
        else:
            L.append(cnt)
if S[-1]=='0':
    L.append(0)

acc=[0]+list(accumulate(L))
mx=0
if cnt0<K:
    K=cnt0
for i in range(0, len(acc), 2):
    if i+(K*2+1)<len(acc):
        mx=max(mx, acc[i+(K*2+1)]-acc[i])
print(mx)
n,k= map(int,input().split())
s = str(input())
if(s[k-1]=="A"):
  s[k-1]="a"
elif(s[k-1]=="B"):
  s[k-1]="b"
else:
  s[k-1]="c"
print(s)

### FIXED CODE ###

n,k = map(int,input().split())
s = str(input())
ans = ""
for i in range(n):
  if(i==k-1):
    if(s[i]=="A"):
      ans+="a"
    elif(s[i]=="B"):
      ans+="b"
    else:
      ans+="c"
  else:
    ans+=s[i]
print(ans)
def read_input():
    a, b, c, d = map(int, input().split())

    return a, b, c, d

def submit():
    a, b, c, d = read_input()

    if b < c or d < a:
        print(0)
        return

    if a < c:
        if d <= b:
            print(d - c)
        else:
            print(b - c)
    else:
        if b <= d:
            print(b - a)
        else:
            print(d - a)



if __name__ == '__main__':
    sub

### FIXED CODE ###


def read_input():
    a, b, c, d = map(int, input().split())

    return a, b, c, d

def submit():
    a, b, c, d = read_input()

    if b < c or d < a:
        print(0)
        return

    if a < c:
        if d <= b:
            print(d - c)
        else:
            print(b - c)
    else:
        if b <= d:
            print(b - a)
        else:
            print(d - a)
    return

if __name__ == '__main__':
    submit()
import math

a,b,c = input().split()

left = a + b
right = c

a = math.sqrt(int(a))
b = math.sqrt(int(b))
#c = math.sqrt(int(c))

left = left + 2*a*b


ans = ""

if(left< right):
    ans = "Yes"
else:
    ans = "No"

print(ans)

### FIXED CODE ###

import math

a,b,c = map(int,input().split())
ans = ""

if((4*a*b)<(c-a-b)*(c-a-b) and c-a-b>0):
    ans = "Yes"
else:
    ans = "No"

print(ans)
a = int(input())
result = 0
for i in range(0, a):
    tmp = 0
    for j in range(0, i):
        if i % j == 0:
            tmp += 1
    if tmp == 8:
        result += 1

print(result)

### FIXED CODE ###

a = int(input())
result = 0
for i in range(0, a):
    tmp = 0
    if (i+1) % 2 != 0:
        for j in range(0, i):
            if (i + 1) % (j + 1) == 0:
                tmp += 1
        if tmp == 7:
            result += 1

print(result)
from functools import reduce
N, M, C = map(int, input().split())
B = map(int, input().split())
count = 0
for _ in range(N):
  	if 0 < C + reduce(lambda p: p[0]*p[1], zip(map(int, input().split()), B)):
    	count += 1
print(count)

### FIXED CODE ###

from functools import reduce
N, M, C = map(int, input().split())
*B, = map(int, input().split())
count = 0
for _ in range(N):
	if 0 < C + reduce(lambda acc, p: acc + p[0]*p[1], zip(map(int, input().split()), B), 0):
		count += 1
print(count)
a,b,c,k = input().split(None, 4)
A = int(a)
B = int(b)
C = int(c)
K = int(k)
X = K - A - B
if K <= A:
    print(K)
elif A < K <= A + B:
    print(A)
else A + B < K:
    print(A - X)

### FIXED CODE ###

a,b,c,k = input().split(None, 4)
A = int(a)
B = int(b)
C = int(c)
K = int(k)
X = K - A - B
if K <= A:
    print(K)
elif A < K <= A + B:
    print(A)
else:
    print(A - X)
from fractions import gcd

def main():
    def fmin(m):
        return X * m + D * m *(m - 1)//2
    def fmax(m):
        return X * m + D * m * (2 * N - m - 1) // 2
    N, X, D = map(int, input().split())
    if D < 0:
        X, D = -X, -D
    if X > 0:
        ans = 0
        g = gcd(X, D)
        loop = D // g
        for d in range(N + 1):
            if loop <= d:
                mmin = max(fmin(d), fmax(d - loop) + D)
            else:
                mmin = fmin(d)
            mmax = fmax(d)
            ans += (mmax - mmin) // D + 1
        print(ans)
    elif X == 0:
        print(fmax(N) // D + 1)
    else:
        ans = 0
        g = gcd(-X, D)
        loop = D // g
        for d in range(N + 1):
            if loop <= d:
                mmax = min(fmax(d), fmin(d - loop) - D)
            else:
                mmax = fmax(d)
            mmin = fmin(d)
            ans += (mmax - mmin) // D + 1
        print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from fractions import gcd

def main():
    def fmin(m):
        return X * m + D * m *(m - 1)//2
    def fmax(m):
        return X * m + D * m * (2 * N - m - 1) // 2
    N, X, D = map(int, input().split())
    if D == 0:
        if X == 0:
            print(1)
        else:
            print(N + 1)
        exit(0)
    if D < 0:
        X, D = -X, -D
    if X > 0:
        ans = 0
        g = gcd(X, D)
        loop = D // g
        for d in range(N + 1):
            if loop <= d:
                mmin = max(fmin(d), fmax(d - loop) + D)
            else:
                mmin = fmin(d)
            mmax = fmax(d)
            ans += (mmax - mmin) // D + 1
        print(ans)
    elif X == 0:
        print(fmax(N) // D + 1)
    else:
        if X + D*(N - 1) >= 0:
            ans = 0
            g = gcd(-X, D)
            loop = D // g
            for d in range(N + 1):
                dmax = fmax(d)
                dmin = fmin(d)
                if d < loop:
                    ans += (dmax - dmin) // D + 1
                else:
                    pmax = fmax(d - loop)
                    pmin = fmin(d - loop)
                    if pmax < dmax and pmin <= dmin:
                        mmin = max(dmin, pmax + D)
                        ans += (dmax - mmin) // D + 1
                    elif pmax >= dmax and pmin > dmin:
                        mmax = min(dmax, pmin - D)
                        ans += (mmax - dmin) // D + 1
                    elif pmax < dmax and pmin > dmin:
                        ans += (dmax - pmax) // D + (pmin - dmin) // D
            print(ans)
                    
        else:
            ans = 0
            g = gcd(-X, D)
            loop = D // g
            for d in range(N + 1):
                if loop <= d:
                    mmax = min(fmax(d), fmin(d - loop) - D)
                else:
                    mmax = fmax(d)
                mmin = fmin(d)
                ans += (mmax - mmin) // D + 1
            print(ans)


if __name__ == '__main__':
    main()
import sys
def input(): return sys.stdin.readline().strip()
n,k,q=map(int,input().split())
pt=[0 for _ in range(n)]
for _ in range(q):
    a = int(input())
    pt[a-1] += 1
base=q-k
for p in pt:
    print("No" if p <= base else "Yes")

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
s=input()
w=["Sunny","Cloudy","Rainy","Sunny"]
print(w[w.index(s)+1])
n,a,b=map(int, input().split())
tmp = 0
if n%a+b>a:
    tmp = a
else:
    tmp = 0
print((n//(a+b))*a+tmp)

### FIXED CODE ###

n,a,b=map(int, input().split())
tmp = n%(a+b)
if tmp>a:
    tmp = a
print((n//(a+b))*a+tmp)
L,R = map(int,input().split())
ans = 1000000000
for i in range(L,R + 1):
	if ans == 0:
		break
		
	for j in range(i,R + 1):
		if ans > i*j % 2019:
			ans = i*j % 2019
			if ans == 0
				break
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())
ans = 10000000000
for i in range(L,R + 1):
	if ans == 0:
		break
		
	for j in range(i + 1,R + 1):
		if ans > i*j % 2019:
			ans = i*j % 2019
			if ans == 0:
				break
print(ans)
H, W=map(int, input().split())
A=[list(map(int, input().split())) for i in range(H)]
B=[list(map(int, input().split())) for i in range(H)]
AB=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
 
G=[[[0]*(80*160+1) for j in range(W)] for i in range(H)]
G[0][0][AB[0][0]]=1
 
for i in range(1, W):
  owari=80*i+1
  G[0][i][:owari]=[1 if G[0][i-1][abs(k-AB[0][i])]+G[0][i-1][abs(k+AB[0][i])]>0 else 0 for k in range(owari+1)]
  
for i in range(1, H):
  owari=80*i+1
  G[i][0][:owari]=[1 if G[i-1][0][abs(k-AB[i][0])]+G[0][i-1][abs(k+AB[i][0])]>0 else 0 for k in range(owari+1)]

from collections import deque

def f(data):
  i=data[0]
  j=data[1]
  tmp=AB[i][j]
  owari=(i+j)*80+1
  G[i][j][:owari+1]=[1 if G[i-1][j][abs(k-AB[i][j])]+G[i-1][j][abs(k+AB[i][j])]+G[i][j-1][abs(k-AB[i][j])]+G[i][j-1][abs(k+AB[i][j])]>0 else 0 for k in range(owari+1)]
  
  if i<H-1:
    q.append([i+1, j])
  if j<W-1:
    q.append([i, j+1])
    
q=deque()
q.append([1, 1])
while len(q)>0:
  data=q.popleft()
  f(data)
  
out=0
while G[-1][-1][out]==0:
  out+=1
print(out)

### FIXED CODE ###

H, W=map(int, input().split())
A=[list(map(int, input().split())) for _ in range(H)]
B=[list(map(int, input().split())) for _ in range(H)]
AB=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]

G=[[[0]*(80*162) for j in range(W)] for i in range(H)]
G[0][0][AB[0][0]]=1
sumi=[[0]*W for i in range(H)]
  
from collections import deque

def f(data):
  i=data[0]
  j=data[1]
  owari=(i+j+1)*80+1
  if i<H-1 and j<W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i+1][j][k+AB[i+1][j]]=1
        G[i+1][j][abs(k-AB[i+1][j])]=1
        G[i][j+1][k+AB[i][j+1]]=1
        G[i][j+1][abs(k-AB[i][j+1])]=1
    if sumi[i+1][j]==0:
      q.append([i+1, j])
      sumi[i+1][j]=1
    if sumi[i][j+1]==0:
      q.append([i, j+1])
      sumi[i][j+1]=1
  elif i>=H-1 and j<W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i][j+1][k+AB[i][j+1]]=1
        G[i][j+1][abs(k-AB[i][j+1])]=1
    if sumi[i][j+1]==0:
      q.append([i, j+1])
      sumi[i][j+1]=1
  elif i<H-1 and j>=W-1:
    for k in range(owari):
      if G[i][j][k]>0:
        G[i+1][j][k+AB[i+1][j]]=1
        G[i+1][j][abs(k-AB[i+1][j])]=1
    if sumi[i+1][j]==0:
      q.append([i+1, j])
      sumi[i+1][j]=1
    
q=deque()
q.append([0, 0])
while len(q)>0:
  data=q.popleft()
  f(data)
  
out=0
while G[-1][-1][out]==0:
  out+=1
print(out)
a,s=int(input().split())
print((s-1)*(a-1))

### FIXED CODE ###

a,s=map(int,input().split())
print((s-1)*(a-1))
a,b,c = map(int, input().split())
if a+b+c >= 22:
print("bust")
else:
    ("win")

### FIXED CODE ###

#ABC147-A #Blackjack                                                                                             
a,b,c = map(int, input().split())
if a+b+c >= 22:
    print("bust")
else:
    print("win")
s, t = map(str, input().split())
a, b = map(int, input().split())
u = input()

balls = {s:a, t:b}

for key in balls:
    if key == u:
        balls[key] = balls[key] - 1

listBalls = list(balls.values())
print(f'{listBalls[0]} {listBalls[1]}')

### FIXED CODE ###

s, t = map(str, input().split())
a, b = map(int, input().split())
u = input()

if s == u:
  a -= 1
else:
  b -= 1

print(a, b)
s, t = input().split()
if s == t[:-1]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s = input()
t = input()
if s == t[:-1]:
  print("Yes")
else:
  print("No")
A, B, C, D = map(int, input().split())
flag == 100
while flag ==100:
    C -= B
    if flag==100 and C<=0:
        flag = 0
    A -= D
    if flag==100 and A<=0:
        flag = 1
if flag==0: print('Yes')
else: print('No')

### FIXED CODE ###

A, B, C, D = map(int, input().split())
flag = 100
while flag ==100:
    C -= B
    if flag==100 and C<=0:
        flag = 0
    A -= D
    if flag==100 and A<=0:
        flag = 1
if flag==0: print('Yes')
else: print('No')
return x * x * x

### FIXED CODE ###

x = input()
cube = x * x * x
print cube
N,K = map(int,input().split())
a = list(map(int,input().split()))
x = []
flg = True
for i in range(N):
    if a[i] > 0 and flg == True:
        x.append(0)
        flg = False
    x.append(a[i])


#x.append(0)
#x.sort()

c = []
for i in range(N - K + 2):
    if (0 not in x[i:i+K+1]) or (len(x[i:i+K+1]) != K+1):
        continue
    p = x[i:i+K+1]
    if min(p) < 0 and max(p) > 0:
        if p[-1] + p[-1] - p[0] < abs(p[0]) + p[-1] -p[0]:
            c.append(p[-1] + (p[-1] - p[0]))
        else:
            c.append(abs(p[0]) + p[-1] - p[0])
    elif min(p) >= 0:
        c.append(p[-1])
    elif max(p) <= 0:
        c.append(abs(p[0]))

print(min(c))


### FIXED CODE ###

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

ans = 10**18
for i in range(N - K + 1):
    p1 = x[i]
    p2 = x[i+K-1]
    lr = abs(p1) + abs(p2 - p1)
    rl = abs(p2) + abs(p1 - p2)
    if lr < rl:
        ans = min(ans,lr)
    else:
        ans = min(ans,rl)
print(ans)
N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
cnt=0
for a in A:
    if a[2]!=0:
        cnt+=1
        ans=a
if cnt=1:
    print(ans)
    exit()
for i in range(101):
    for j in range(101):
        hi=[]
        flg=True

        for a in A:
            if a[2]!=0:
                hi_=a[2]+abs(a[1]-j)+abs(a[0]-i)
                hi.append(hi_)

            if len(hi)>=2:
                if hi[-1]!=hi[-2]:
                    flg=False
        #print(i,j,hi)
        if flg:
            ans=[i,j,hi[0]]

print(*ans)


### FIXED CODE ###

N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
cnt=0
for a in A:
    if a[2]!=0:
        cnt+=1
        ans=a
if cnt==1:
    print(*ans)
    exit()
for i in range(101):
    for j in range(101):
        hi=[]
        flg=True

        for a in A:
            if a[2]!=0:
                hi_=a[2]+abs(a[1]-j)+abs(a[0]-i)
                hi.append(hi_)

            if len(hi)>=2:
                if hi[-1]!=hi[-2]:
                    flg=False
        #print(i,j,hi)
        if flg:
            ans=[i,j,hi[0]]

print(*ans)
k = int(input())
a, b = map(int,input().split())
n = 1
flag = True
while (k*n) <= b:
    if (k*n) >= a and (k*n) <= b:
        ans = "OK"
        break
    else:
        ans = "NG"
    n += 1
print(ans)

### FIXED CODE ###

k = int(input())
a, b = map(int,input().split())
n = 1
ans = "NG"
while (k*n) <= b:
    if (k*n) >= a and (k*n) <= b:
        ans = "OK"
        break
    n += 1
print(ans)
N, M, K = map(int, input().split())

ans = 0

for i in range(K+1):
    ans += M ** (i+1) * (M-1) ** (N-i-1)
    ans %= MOD

print(ans)

### FIXED CODE ###


from collections import defaultdict

MOD = 998244353

def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    return fact[a] * ifact[b] * ifact[a-b]


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

# 階乗を前処理
fact = defaultdict(int)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD
# 階乗の逆元を前処理
ifact = defaultdict(int)
ifact[N] = pow(fact[N], MOD-2, MOD)
for i in reversed(range(1, N + 1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD

ans = 0
color = M
for x in reversed(range(N)):
    now = color
    now *= combination(N-1, x)
    now %= MOD
    if x <= K:
        ans += now
        ans %= MOD
    color *= M - 1
    color %= MOD

print(ans)
a,b=map(int,input().split())
if (a+b)%2===0:
    print((a+b)//2)
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

a,b=map(int,input().split())
if (a+b)%2==0:
    print((a+b)//2)
else:
    print("IMPOSSIBLE")
N,K=map(int, input().split())
Candles=list(map(int, input().split()))

Distance=[]
for i in range(N-K):
        Distance.append(abs(Candles[i]-Candles[i+K-1])+min(abs(Candles[i]),abs(Candles[i+K-1])))
print(min(Distance))

### FIXED CODE ###

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

Distance=[]
for i in range(N-K+1):
        Distance.append(abs(Candles[i]-Candles[i+K-1])+min(abs(Candles[i]),abs(Candles[i+K-1])))
print(min(Distance))
from heapq import heappop,heappush
n = int(input())
A = sorted(list(map(int,input().split())))
P = []
M = []
if n == 2:
    print(A[1]-A[0])
    print(A[1],A[0])
    exit()
def move():
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
for a in A:
    if a>0:
        P.append(a)
    else:
        M.append(a)
if all(a == 0 for a in A):
    print(0)
    for i in range(n-1):
        print(0,0)
    exit()
if A[-1]>=0 and A[0]<=0:
    print(sum(abs(a) for a in A))
elif A[0]>=0:
    print(sum(A)-min(A)*2)
    mm = heappop(P)
    pp = heappop(P)
    print(mm,pp)
    heappush(M,mm-pp)
else:
    print(sum(abs(a) for a in A)+max(A)*2)
    mm = M[-1]
    pp = M[-2]
    print(mm,pp)
    M = M[:-2]
    heappush(P,mm-pp)
move()

### FIXED CODE ###

from heapq import heappop,heappush
n = int(input())
A = sorted(list(map(int,input().split())))
P = []
M = []
if n == 2:
    print(A[1]-A[0])
    print(A[1],A[0])
    exit()
def move():
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
for a in A:
    if a>=0:
        P.append(a)
    else:
        M.append(a)

if A[-1]>=0 and A[0]<0:
    print(sum(abs(a) for a in A))
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
elif A[0]>=0:
    print(sum(A)-min(A)*2)
    mm = heappop(P)
    pp = heappop(P)
    print(mm,pp)
    heappush(M,mm-pp)
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
else:
    print(sum(abs(a) for a in A)+max(A)*2)
    mm = M[-1]
    pp = M[-2]
    print(mm,pp)
    M = M[:-2]
    heappush(P,mm-pp)
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
D, n = map(int.input().split())

for i in range(n):
    A[i] = input()
    i += 1
    D_sum += A[i]
    x = D - D_sum
print()

### FIXED CODE ###

N, M = map(int,input().split())
#M 夏休み期間　M　宿題数
A = list(map(int, input().split()))
A_sum = 0
for i in range(0, M):
    A_sum += A[i]
    # A_sum 宿題全日数
x = N - A_sum
if x < 0:
    print("-1")
else:
    print(x)
# -*- coding: utf-8 -*-

import random
def qui(l):
    num = len(l)
    if num <= 1:
        return l
    piv = random.randrange(0,len(l))
    piv2 = random.randrange(0,len(l))
    piv3 = random.randrange(0,len(l))
    if (l[piv] > l[piv2]) and (l[piv2] > l[piv3]):
        piv = piv2
    elif (l[piv] > l[piv3]) and (l[piv3] > l[piv2]):
        piv = piv3
    elif (l[piv] < l[piv2]) and (l[piv2] < l[piv3]):
        piv = piv2
    elif (l[piv] < l[piv3]) and (l[piv3] < l[piv2]):
        piv = piv3
    else:
        pass
    mini = []
    maxi = []

    for i in range(0,len(l)):
        if i == piv:
            continue
        elif l[piv] > l[i]:
            mini.append(l[i])
        elif l[piv] <= l[i]:
            maxi.append(l[i])
    mini = qui(mini)
    maxi = qui(maxi)
    return mini+maxi
input()
list1 = input().split(" ")
for i in range(0, len(list1)):
    list1[i] = int(list1[i])

result = qui(list1)

print(' '.join(map(str, result)))

### FIXED CODE ###

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

import random
def qui(l):
    num = len(l)
    if num <= 1:
        return l
    piv = random.randrange(0,len(l))
    piv2 = random.randrange(0,len(l))
    piv3 = random.randrange(0,len(l))
    if (l[piv] > l[piv2]) and (l[piv2] > l[piv3]):
        piv = piv2
    elif (l[piv] > l[piv3]) and (l[piv3] > l[piv2]):
        piv = piv3
    elif (l[piv] < l[piv2]) and (l[piv2] < l[piv3]):
        piv = piv2
    elif (l[piv] < l[piv3]) and (l[piv3] < l[piv2]):
        piv = piv3
    else:
        pass
    mini = []
    middlei = []
    maxi = []

    for i in range(0,len(l)):
        if l[i] == l[piv]:
            middlei.append(l[i])
        elif l[piv] > l[i]:
            mini.append(l[i])
        elif l[piv] <= l[i]:
            maxi.append(l[i])
    mini = qui(mini)
    maxi = qui(maxi)
    return mini+ middlei+maxi
input()
list1 = input().split(" ")
for i in range(0, len(list1)):
    list1[i] = int(list1[i])

result = qui(list1)

print(' '.join(map(str, result)))
s = list(input())
print(s.count('1')

### FIXED CODE ###

s = list(input())
print(s.count('1'))
n,m=map(int,input().split())
g=[[] for i in range(1+n)]
dist=[-1]*(1+n)
for i in range(m):
    a,b=map(int,input().split())
    g[a].append(b)
    
def dfs(cur):
    if dist[cur]!=-1:
        return dist[cur]
        
    if not g[cur]:
        dist[cur]=0
    else:
        dist[cur]=1+max([dfs(nb) for nb in g[cur]])
    return dist[cur]

ans=0
for i in range(1,n+1):
    ans=max(ans,dfs(i))

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for i in range(1+n)]
dist=[-1]*(1+n)
for i in range(m):
    a,b=map(int,input().split())
    g[a].append(b)
    
def dfs(cur):
    if dist[cur]!=-1:
        return dist[cur]
        
    if not g[cur]:
        dist[cur]=0
    else:
        dist[cur]=1+max([dfs(nb) for nb in g[cur]])
    return dist[cur]

ans=0
for i in range(1,n+1):
    ans=max(ans,dfs(i))

print(ans)
# -*- coding: utf-8 -*-
#import numpy as np
def fnSolv():
  iNum, iK = map(int, input().split())
  lHn  = list(map(int, input().split()))
  lDP  = [0]*iK
  lLen = [0]*len(lRange)
  for iI0 in range(1, iNum):
    lRange = range(max([0, iI0 - iK]), iI0)
    iLen = len(lRange)
    for iI2, iI1 in enumerate(lRange):
      lLen[iI2] = lDP[iI1%iK] + abs(lHn[iI0] - lHn[iI1])
    lDP[iI0%iK] = min(lLen[:iLen])
    #print(iI0, lDP, lLen)
  print(lDP[(iNum-1)%iK])

if __name__ == '__main__':
  fnSolv()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
def fnSolv():
  iNum, iK = map(int, input().split())
  naHn  = np.array(list(map(int, input().split())))
  naDP  = np.zeros(iNum, dtype='int64')
  naLen = np.ones(iK) * 10**9
  for iI0 in range(1, iNum):
    iK0 = min([iK, iI0])
    naLen = naDP[iI0-iK0:iI0] + np.abs(- naHn[iI0-iK0:iI0] + naHn[iI0])
    naDP[iI0] = naLen.min()
  print(naDP[iNum-1])

if __name__ == '__main__':
  fnSolv()