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

import sys
sys.setrecursionlimit(500000)
n,q=map(int,input().split())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
ans=[0 for i in range(n)]
for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x
def dsf(index,u):
  for i in l[index]:
    if i==u:continue
    ans[i]+=ans[index]
    dsf(i,index)
dsf(0,-1)
print(' '.join(str(j) for j in ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
n,q=map(int,input().split())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
px=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  px[p-1]+=x
ans=[0]*n
def dsf(index,u):
  ans[index]=ans[u]+px[index]
  for i in l[index]:
    if i==u:continue
    dsf(i,index)
dsf(0,-1)
print(*ans)
### BUGGY CODE ###

from collections import Counter, deque, defaultdict

n, x, y = map(int, input().split())

v = defaultdict(list)
for i in range(n):
    if i + 1 < n: v[i].append(i + 1)
    if i - 1 >= 0: v[i].append(i - 1)
v[x - 1].append(y - 1)
v[y - 1].append(x - 1)

cnt = Counter()
for start in range(n):
    dist = [float("inf")] * n
    q = deque()
    q.append([start, 0])
    while q:
        c, d = q.popleft()
        for next in v[c]:
            if dist[next] == float("inf"):
                q.append([next, d + 1])
                dist[next] = d + 1
    cnt += Counter(dist[start + 1:])

for i in range(1, n):
    print(cnt[i])


### FIXED CODE ###

from collections import Counter, deque, defaultdict


def main():
    n, x, y = map(int, input().split())
    v = defaultdict(list)
    for i in range(n):
        if i + 1 < n: v[i].append(i + 1)
        if i - 1 >= 0: v[i].append(i - 1)
    v[x - 1].append(y - 1)
    v[y - 1].append(x - 1)

    cnt = Counter()
    for start in range(n):
        dist = [-1] * n
        q = deque()
        q.append([start, 0])
        while q:
            c, d = q.popleft()
            for next in v[c]:
                if dist[next] == -1:
                    q.append([next, d + 1])
                    dist[next] = d + 1
        cnt += Counter(dist[start + 1:])

    for i in range(1, n):
        print(cnt[i])


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

S = list(input())
MOD = 10 ** 9 + 7

dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] == '?':
        s = -1
    else:
        s = int(S[i])

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
    for l in range(13):
        dp[i + 1][l] %= MOD

print(dp[len(S)][5])


### FIXED CODE ###

S = list(input())
MOD = 10 ** 9 + 7

length = len(S)
dp = [[0] * 13 for _ in range(length + 1)]
dp[0][0] = 1

for i in range(length):
    if S[i] == '?':
        s = -1
    else:
        s = int(S[i])

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            index = (k * 10 + j) % 13
            dp[i + 1][index] = (dp[i + 1][index] + dp[i][k]) % MOD

print(dp[length][5])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = input()
ans = 0

for i in range(1000):
    cnt = 0
    if i < 100:
        if i < 10:
            match = '00' + str(i)
        else:
            match = '0' + str(i)
    else:
        match = str(i)

    for j in range(len(s)):
        if s[j] == match[cnt]:
            cnt += 1

        if cnt == 3:
            ans += 1
            break

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = input()
ans = 0

for i in range(1000):
    cnt = 0
    if i < 100:
        if i < 10:
            match = '00' + str(i)
        else:
            match = '0' + str(i)
    else:
        match = str(i)

    for S in s:
        if S == match[cnt]:
            cnt += 1

        if cnt == 3:
            ans += 1
            break

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

# import numpy as np
from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[input() for _ in range(H)]
# 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
S = ['##{}##'.format(row) for row in S]
S.insert(0, '##{}##'.format('#' * W))
S.insert(0, '##{}##'.format('#' * W))
S.append('##{}##'.format('#' * W))
S.append('##{}##'.format('#' * W))


MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
# Cost = np.full((H,W),MAX_COST)

# print(S)

ans = -1

cost0 = deque()

cost0.append((CH+1,CW+1,0))
Cost[CH+1][CW+1] = 0;

# used = set()
walk=[(1,0),(0,1),(-1,0),(0,-1)]
warp = [ (i,j) for i in range(-2,3) for j in range(-2,3) if (i, j) not in [(0, 0)] + walk ]
# print(warp)

cost1 = deque()

while 0 < len(cost0):
	h,w,c=cost0.popleft()
	cost1.append((h,w,c))

	for i,j in walk:
		dh = h+i
		dw = w+j
		if S[dh][dw] == '.' and c < Cost[dh][dw]:
			Cost[dh][dw] = c
			# print("updl ", i,j,dh,dw,c)
			cost0.appendleft((dh,dw,Cost[dh][dw]))

	if len(cost0) == 0:

		while 0 < len(cost1):
			h,w,c=cost1.popleft()
			# print(h,w,c)
			for i,j in warp:
				dh = h+i
				dw = w+j
				# print(i,j)
				if S[dh][dw] == '.' and c + 1 < Cost[dh][dw]:
					Cost[dh][dw] = c + 1
					cost0.append((dh,dw,Cost[dh][dw]))


if Cost[DH+1][DW+1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH+1][DW+1])

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])
### BUGGY CODE ###

N, K = [int(x) for x in input().strip().split(" ")]
A = [int(x) for x in input().strip().split(" ")]

def mul(A):
    b = 1
    for a in A:
        b *= a
    return b

scores = [mul(A[i-K+1:i+1]) for i in range(K-1, N)]

for i, S in enumerate(scores):
    if i == 0:
        continue
    if S > scores[i - 1]:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N, K = [int(x) for x in input().strip().split(" ")]
A = [int(x) for x in input().strip().split(" ")]

for i in range(K, N):
    if A[i] > A[i-K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
stdin = sys.stdin
from math import sqrt

def li(): return map(int, stdin.readline().split())

def gcd(A, B):
    if B > A:
        return gcd(B, A)
    while B != 0:
        A, B = B, A - B
    return A

def test_gcd():
    assert gcd(8, 4) == 4


A, B, K = tuple(li())
count = 0
g = gcd(A, B)
can = set()
for i in range(1, int(sqrt(g)) + 1):
    if g % i == 0:
        can.add(i)
        can.add(g // i)
can = sorted(can, reverse=True)
print(can[K - 1])




### FIXED CODE ###

import sys
stdin = sys.stdin
from math import sqrt

def li(): return map(int, stdin.readline().split())




A, B, K = tuple(li())
count = 0
g = min(A, B)
can = []
cnt = 0
for i in range(1, g + 1):
    if A % i == 0 and B % i == 0:
        
        
        can.append(i)



print(can[-K])
### BUGGY CODE ###

import sys

input = sys.stdin.buffer.readline
n, s = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]

mod = 998244353
# dp[i][s] A[i]まで見た時、合計sになる数。
# 各々の地点で新しく開始されるものも有るので毎回dp[i][0]は＋1
dp[0][0] = 1
ans = 0
for i in range(n):
    ni = i + 1
    for j in range(s + 1):
        nj = j
        dp[ni][nj] += dp[i][j]
        dp[ni][nj] %= mod
        nj = j + A[i]
        if nj <= s:
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
    dp[ni][0] += 1
    ans += dp[ni][s]
    ans %= mod
print(ans)


### FIXED CODE ###

n, s = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]

mod = 998244353
# dp[i][s] A[i]まで見た時、合計sになる数。
# 各々の地点で新しく開始されるものも有るので毎回dp[i][0]は＋1
dp[0][0] = 1
ans = 0
for i in range(n):
    ni = i + 1
    for j in range(s + 1):
        nj = j
        dp[ni][nj] += dp[i][j]
        dp[ni][nj] %= mod
        nj = j + A[i]
        if nj <= s:
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
    dp[ni][0] += 1
    ans += dp[ni][s]
    ans %= mod
print(ans)
### BUGGY CODE ###

import sys
s = input()
q = int(input())
for _ in range(q):
    qi = input()
    if len(qi) <= 2:
        s = s[::-1]
    else:
        _,F,C = qi.split()
        if F == "1":
            s = C + s
        else:
            s = s + C           
print(s)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

t = deque(S)
reverse = False
for _ in range(Q):
    query = input()
    if query[0] == '1':
        reverse = not reverse
    elif query[0] == '2':
        _, F, C = query.split()
        if F == '1':
            if reverse:
                t.append(C)
            else:
                t.appendleft(C)
        elif F == '2':
            if reverse:
                t.appendleft(C)
            else:
                t.append(C)
result = ''.join(t)
if reverse:
    result = result[::-1]
print(result)
### BUGGY CODE ###

import math
n = int(input())
nlist = list(map(int,input().split()))
 
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
 
countlist = [0]*(len(nlist) + 1)
for i in range(0,len(nlist) + 1):
    countlist[i] = nlist.count(i)
 
count = 0
for i in range(0,len(nlist)):
    if countlist[i] >= 2:
        count+=combinations_count(countlist[i],2)
 
anslist = []
 
for i in range(0,len(nlist)):
    anslist.append((count-countlist[nlist[i]])+1)
 
for i in anslist:
    print(i)

### FIXED CODE ###

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

import collections

count_dict=collections.Counter(nlist)

anslist=[]
all_kumi=0
for i in count_dict.values():
    all_kumi += i*(i-1)//2
 
for j in range(0,n):
    print(all_kumi - count_dict[nlist[j]] + 1)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[6]:


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


# In[7]:


ans = (10**9)*N
for i in range(1,N):
    x = sum(a[:i])
    y = sum(a[i:])
    ans = min(ans,abs(x-y))
    if ans < 2:
        break
print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[11]:


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


# In[12]:


ans = (10**9)*N
x = 0
y = sum(a)
for i in range(N-1):
    x += a[i]
    y -= a[i]
    ans = min(ans,abs(x-y))
    if ans < 2:
        break
print(ans)


# In[ ]:
### BUGGY CODE ###

s = input()
q = int(input())
jun = 1
for _ in range(q):
  
  tmp = input()
  if len(tmp)==1:
    jun = 1 if jun==0 else 0 
  else:
    _,f,c = tmp.split()
    if jun+int(f) ==2:
      s = c+s
    else:
      s += c
if jun==1:
  print(s)
else:
  print(s[::-1])
      
    


### FIXED CODE ###

s = input()
q = int(input())
jun = 1
f = "";t = ""
for _ in range(q):
  
  tmp = input()
  if len(tmp)==1:
    jun = 1 if jun==0 else 0 
  else:
    _,ff,c = tmp.split()
    if jun+int(ff) ==2:
      f = c+f
    else:
      t += c
if jun==1:
  print(f+s+t)
else:
  print((f+s+t)[::-1])
### BUGGY CODE ###

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
import sys

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N = ii()
S = si()

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i)
    if S[i] == 'G':
        G.append(i)
    if S[i] == 'B':
        B.append(i)

colors = [
    [R, G, B],
    [R, B, G],
    [G, R, B],
    [G, B, R],
    [B, R, G],
    [B, G, R],
]

ans = 0

for C1, C2, C3 in colors:
    for c1 in C1:
        for c2 in C2:
            if c1 > c2:
                continue
            for c3 in C3:
                if c2 > c3:
                    continue
                if c1 > c3:
                    continue
                if c2 - c1 != c3 - c2:
                    ans += 1

print(ans)

### FIXED CODE ###

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N = ii()
S = si()

r_cnt = S.count('R')
g_cnt = S.count('G')
b_cnt = S.count('B')

ans = r_cnt * g_cnt * b_cnt

for i in range(N):
    for dist in range(N):
        j = i + dist
        k = j + dist
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1

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

from sys import stdin
 
N = int(stdin.readline().rstrip())
 
A = [int(x) for x in stdin.readline().rstrip().split()]
 
for a in range(N):  
  B = sorted([elem for idx,elem in enumerate(A) if idx != a])
  print(B[(N-1)//2])

### FIXED CODE ###

from sys import stdin
 
N = int(stdin.readline().rstrip())
 
A = [int(x) for x in stdin.readline().rstrip().split()]

B = sorted(A)
 
for i in range(N):  
  if A[i] < B[N//2]:
    print(B[N//2])
  else:
    print(B[N//2-1])
### BUGGY CODE ###

def common_multiple(x, y):
    for i in range(2, min(x, y)+1):
        if x % i == 0 and y % i == 0:
            return common_multiple(x // i, y // i) * i
    return x * y

a = input().split(" ")
A, B, C, D = int(a[0]) - 1, int(a[1]), int(a[2]), int(a[3])

M = common_multiple(C, D)
B0 = B // C + B // D - B // M
A0 = A // C + A // D - A // M
print(B - A - B0 + A0)


### FIXED CODE ###

def common_multiple(x, y):
    for i in range(2, min(x, y)+1):
        mod_x = x % i
        mod_y = y % i
        if (mod_x == 0 and mod_y == 0):
            return common_multiple(x // i, y // i) * i
        if (mod_x == 0):
            return common_multiple(x // i, y) * i
        if (mod_y == 0):
            return common_multiple(x, y // i) * i
    return  x * y

a = input().split(" ")
A,B,C,D=int(a[0]) - 1,int(a[1]),int(a[2]),int(a[3])

M = common_multiple(C,D)
B0 = B // C + B // D - B // M
A0 = A // C + A // D - A // M
print(B - A - B0 + A0)
### BUGGY CODE ###

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

import math
for i in range(m):
    a.sort(reverse = True)
    a[0] = a[0]/2

import math
print(sum(list(map(math.floor,a))))

### FIXED CODE ###

(n,m) = tuple(map(int,input().split()))
b = list(map(int,input().split()))
a = list(map(lambda x:x*(-1),b))

import heapq
heapq.heapify(a)

temp = 0
for i in range(m):
    temp = heapq.heappop(a)
    heapq.heappush(a,temp/2)

import math
c = list(map(lambda x:x*(-1),a))
print(sum(list(map(math.floor,c))))
### BUGGY CODE ###

import re
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

answer=0
for s in itertools.product('ATGC', repeat=N):
  answer += not repattern.search(''.join(s))

print(answer)

import numpy

### FIXED CODE ###

import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
  	memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.values())%(10**9+7))
### BUGGY CODE ###

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

ans = 1
flag = 0
for i in li:
  ans *= i

if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

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

"""
ans = 1
flag = 0
for i in li:
  if i == 0:
    flag = 1
    break
  ans *= i

if flag == 1:
  print(0)
elif ans > 10**18:
  print(-1)
else:
  print(ans)
"""
ans = 1
flag = 0
li.sort()
if li[0] == 0:
  print(0)
else:
  for i in li[::-1]:
    ans *= i
    if ans > 10**18:
      flag = 1
      break

  if flag == 0:
    print(ans)
  elif flag == 1:
    print(-1)
### BUGGY CODE ###

s = input()

ans = []
k = s.find("LR")
while k!=-1:
    t = s[:k+1]
    a = [0]*len(s[:k+1])
    numR = t.count("R")
    numL = t.count("L")
    l = numR-1
    a[l] = (numR+1)//2 + (numL)//2
    a[l+1] = (numR)//2 + (numL+1)//2
    ans = ans + a
    s = s[k+1:]
    k = s.find("LR")

a = [0]*len(s)
numR = s.count("R")
numL = s.count("L")
l = numR-1
a[l] = (numR+1)//2 + (numL)//2
a[l+1] = (numR)//2 + (numL+1)//2
ans = ans + a
print(" ".join(list(map(str, ans))))

### FIXED CODE ###

s = input()
l = len(s)
ans = [0]*l
count = 0
for i in range(l):
    if s[i]=="R" and s[i+1]=="R":
        count += 1
    elif s[i]=="R" and s[i+1]=="L":
        count += 1
        ans[i] += (count+1)//2
        ans[i+1] += count//2
        count = 0
for i in reversed(range(l)):
    # print(i)
    # print(s[i])
    if s[i]=="L" and s[i-1]=="L":
        count += 1
    elif s[i]=="L" and s[i-1]=="R":
        count += 1
        ans[i] += (count+1)//2
        ans[i-1] += count//2
        count = 0
print(" ".join(map(str, ans)))
### BUGGY CODE ###

S = list(input())
n = len(S)

count = 0
while True:
    DID = False
    for i in range(n-1):
        if S[i] == "B" and S[i+1] == "W":
            S[i] = "W"
            S[i+1] = "B"
            count += 1
            DID = True

    if not DID:
        break

print(count)

### FIXED CODE ###

S = input()

count = 0
out = 0
for cur_i, s in enumerate(S):
    if s == "W":
        out += (cur_i - count)
        count += 1

print(out)
### BUGGY CODE ###

def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)

    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1

    f = []
    for i in range(n):
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        f.append(b)

    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        if t in f[i]:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(f[i])]
    return -1


print(BC132_E())

### FIXED CODE ###

def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    a, b = set(), set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        v = set()
        for j in e[i]:
            if j in a: continue
            a.add(j)
            for k in e[j]:
                if k in b: continue
                b.add(k)
                v.update(e[k])
        if t in v:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(v)]
    return -1


print(BC132_E())
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for l in range(k+1):
    for m in range(k+1):
        for n in range(k+1):
            if l + m + n == s:
                ans += 1
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for l in range(k+1):
    for m in range(k+1):
        if 0 <= s - (l + m) <= k:
            ans += 1
print(ans)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
N,K=map(int,input().rstrip().split())
h=list(map(int,input().rstrip().split()))

inf=10**9+7
dp=[inf]*N
dp[0]=0

for i in range(1,N,1):
    for k in range(1,K+1,1):
        if(i-k<0):
            continue
        dp[i]=min(dp[i],dp[i-k]+abs(h[i]-h[i-k]))
print(dp[N-1])
  

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().rstrip().split())
h=list(map(int,input().rstrip().split()))

inf=10**9+7
dp=[inf]*N
dp[0]=0

for i in range(1,N,1):
    for k in range(1,K+1,1):
        if(i-k<0):
            continue
        dp[i]=min(dp[i],dp[i-k]+abs(h[i]-h[i-k]))
print(dp[N-1])
### BUGGY CODE ###

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

def dp(cost):
    for x in range(1,N):
        cost[x] =  min( [ cost[k] + abs( h[x] - h[k] ) for k in range(max(x-K,0),x) ] ) 
    return 0

def solve():
    cost = [float('inf')] * N
    cost[0] = 0
    dp(cost)
    print(cost[N-1])
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

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

def dp(cost):
    for x in range(1,N):
        for k in range(max(x-K,0),x):
            cost[x] = min(cost[x] , cost[k] + abs( h[x] - h[k] ) )
        # cost[x] =  min( [ cost[k] + abs( h[x] - h[k] ) for k in range(max(x-K,0),x) ] ) 
    return 0

def solve():
    cost = [float('inf')] * N
    cost[0] = 0
    dp(cost)
    print(cost[N-1])
    return 0

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

A,B,N = map(int,input().split())
x = N
a = 0
while x>N//2:
  if x%B != 0 and a < A*x//B - A*(x//B):
    a = A*x//B - A*(x//B)
    x -= 1
  else:
    x -= 1
print(a)

### FIXED CODE ###

A,B,N = map(int,input().split())
x = min(N, B-1)
a = A*x//B - A*(x//B)
print(a)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
# 先頭に0番要素を追加すれば、配列の要素番号と入力pが一致する
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

ans = -1e9*1e9
s = [None] * n
# 開始ノードをsi
for si in range(1, n+1):

    # 閉ループのスコアを取り出す
    x = si
    #s = list()  # ノードの各スコアを保存
    s_len = 0
    tot = 0     # ループ1周期のスコア
    while 1:
        x = p[x]
        #s.append(c[x])
        s[s_len] = c[x]
        s_len += 1
        tot += c[x]
        if (x == si): break # 始点に戻ったら終了
    
    # siを開始とする閉ループのスコア(s)を全探
    #s_len = len(s)
    t = 0
    for i in range(s_len):
        t += s[i]   # i回移動したときのスコア
        if (i+1 > k): break # 移動回数の上限を超えたら終了
        # 1周期のスコアが正ならば、可能な限り周回する
        if tot > 0:
            e = (k-(i+1))//s_len # 周回数
            now = t + tot*e      # i回移動と周回スコアの合計
        else:
            now = t
        ans = max(ans, now)

print(ans)


### FIXED CODE ###

n, k = list(map(int, input().split()))
# 先頭に0番要素を追加すれば、配列の要素番号と入力pが一致する
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

ans = -float('inf')
# 開始ノードをsi
for si in range(1, n+1):

    # 閉ループのスコアを取り出す
    x = si
    s = list()  # ノードの各スコアを保存
    #s_len = 0
    tot = 0     # ループ1周期のスコア
    while 1:
        x = p[x]
        s.append(c[x])
        #s[s_len] = c[x]
        #s_len += 1
        tot += c[x]
        if (x == si): break # 始点に戻ったら終了
    
    # siを開始とする閉ループのスコア(s)を全探
    s_len = len(s)
    t = 0
    for i in range(s_len):
        t += s[i]   # i回移動したときのスコア
        if (i+1 > k): break # 移動回数の上限を超えたら終了
        # 1周期のスコアが正ならば、可能な限り周回する
        if tot > 0:
            e = (k-(i+1))//s_len # 周回数
            now = t + tot*e      # i回移動と周回スコアの合計
        else:
            now = t
        ans = max(ans, now)

print(ans)