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

import sys
#import numpy as np
#from collections import defaultdict
import math
#from collections import deque

input = sys.stdin.readline



def main():


    N ,K= map(int,input().split())
    H = list(map(int,input().split()))
    H = [0] + H
    dp= [0] *(N+1)
    dp = [math.inf] * (N + 1)
    dp[1] = 0

    for i in range(2, N + 1):
        way =[]
        for j in range(1, K+1):
            if j<i:
                way.append(dp[i-j]+abs(H[i]-H[i-j]))
        dp[i] = min(way)


    print(dp[N])





if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
#import numpy as np
#from collections import defaultdict
#import math
#from collections import deque

input = sys.stdin.readline



def main():


    N ,K= map(int,input().split())
    H = list(map(int,input().split()))
    H = [0] + H
    dp= [0] *(N+1)
    dp = [10**5] * (N + 1)
    dp[1] = 0

    for i in range(2, N + 1):
        way =[10**10]*(K+2)
        for j in range(1, K+1):
            if j<i:
                way[j]=(dp[i-j]+abs(H[i]-H[i-j]))
        dp[i] = min(way)


    print(dp[N])





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

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [sum(range(1, p+1))/p for p in P]

cumsum = [0]*(N+1)
for i in range(1, N+1):
    cumsum[i] = cumsum[i-1] + P[i-1]
ans = 0
for i in range(N-K+1):
    if ans < cumsum[i+K]-cumsum[i]:
        ans = cumsum[i+K]-cumsum[i]
print(ans) 

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [(1+p)/2 for p in P]

cumsum = [0]*(N+1)
for i in range(1, N+1):
    cumsum[i] = cumsum[i-1] + P[i-1]
ans = 0
for i in range(N-K+1):
    if ans < cumsum[i+K]-cumsum[i]:
        ans = cumsum[i+K]-cumsum[i]
print(ans)
### BUGGY CODE ###

N = int(input())
line = list(map(int, input().split()))
dic = set(line)
nums = 0
for i in dic:
    cnt = line.count(i) - 1
    nums += (cnt * (cnt + 1)) // 2

for i in line:
    cnt = line.count(i) - 1
    print(nums - cnt)


### FIXED CODE ###

from collections import Counter
import time

N = int(input())
line = list(map(int, input().split()))
dic = Counter(line)
nums = 0
for num, cnt in dic.items():
    if cnt > 1:
        nums += (cnt * (cnt - 1)) // 2
for i in line:
    print(nums - (dic[i] - 1))
### BUGGY CODE ###

n = int(raw_input())
A = map(int, raw_input().split())
q = int(raw_input())
M = map(int, raw_input().split())

def solve(i,m):
    if m == 0:
        return 1
    if i >= n:
        return 0
    res = solve(i+1, m) or solve(i+1, m-A[i])
    return res

def main():
    for m in M:
        res = solve(0,m)
        if res:
            print 'yes'
        else:
            print 'no'

main()
    

### 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'
### BUGGY CODE ###

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

b=[]
for i in range(n):
    b.append(a[i])
    b=b[::-1]
print(' '.join(map(str,b)))


### FIXED CODE ###

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

odd = []
even = []
for i in range(n):
    if i%2==0:
        even.append(a[i])
    else:
        odd.append(a[i])
if n%2!=0:
    b=even[::-1]+odd
else:
    b=odd[::-1]+even

print(' '.join(map(str,b)))
### BUGGY CODE ###

import copy
def main():
    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)]
    c = [[None]*w for _ in range(h)]
    for i in reversed(range(h)):
        for j in reversed(range(w)):
            c[i][j] = abs(a[i][j] - b[i][j])
            if i < h-1:
                c[i][j] += c[i+1][j]
            if j < w-1:
                c[i][j] += c[i][j+1]
    dp = [set() for i in range(w)]
    dp[0].add(abs(a[0][0] - b[0][0]))
    for j in range(1, w):
        x = abs(a[0][j] - b[0][j])
        for v in dp[j-1]:
            dp[j].add(v + x)
            dp[j].add(abs(v - x))
    for i in range(1, h):
        for j in range(w):
            m = (h-1-i) + (w-1-j) + 1
            x = abs(a[i][j] - b[i][j])
            if j == 0:
                buf = copy.deepcopy(dp[j])
                dp[j].clear()
                for v in buf:
                    if 80*m < v:
                        continue
                    dp[j].add(v + x)
                    dp[j].add(abs(v - x))
            else:
                buf = dp[j-1] | dp[j]
                dp[j].clear()
                for v in buf:
                    if 80*m < v:
                        continue
                    dp[j].add(v + x)
                    dp[j].add(abs(v - x))
    ans = float("inf")
    for v in dp[w-1]:
        ans = min(ans, abs(v))
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
def main():
    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)]
    n = 80*(80+80) + 10
    m = n//2
    dp = [[None]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j] = np.zeros(n, np.bool)
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if 0 < i and 0 < h:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
            elif 0 < i:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
            elif 0 < j:
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
    ans = float("inf")
    for i in range(m-80-1, m+80+2):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

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

N = int(input())
S =input()

ans = float('inf')

for i in range(N):
    s1 = S[0:i]
    s2 = S[i+1:N]
    cnt = s1.count('W') + s2.count('E')
    ans = min(ans, cnt)

print(ans)

### FIXED CODE ###

N = int(input())
S =input()

cntW, cntE = 0, S[1:].count('E')
ans = cntW + cntE
 
for i in range(N-1):
    if S[i+1] == 'E':
        cntE = cntE - 1 
    if S[i] == 'W':
        cntW = cntW + 1
    cnt = cntE + cntW
    ans = min(ans, cnt)

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

S=list(input())
c=0
l=["01", "10"]
while len(S)>1:
    before=len(S)
    for i in range(before-1):
        #if S[i]+S[i+1]=="01" or S[i]+S[i+1]=="10":
        if S[i]+S[i+1] in l:
            c+=2
            #S.pop(i)
            #S.pop(i)
            del S[i:i+2]
            break
    if before==len(S):
        break
print(c)


### FIXED CODE ###

S=input()
print(2*min(S.count("0"), S.count("1")))
### BUGGY CODE ###

input()
a=list(map(int,input().split()))
b=int(input())
for i in range(b):
  n,m=map(int,input().split())
  a=[m if i==n else i for i in a]
  print(sum(a))

### FIXED CODE ###

from sys import stdin
input=stdin.readline
input()
a=list(map(int,input().split()))
ans=sum(a)
b=[0]*(10**5+1)
for i in a:
  b[i]+=1
c=int(input())
for i in range(c):
  n,m=map(int,input().split())
  if b[n]>0:
    x=b[n]
    if x>0:
      b[m]+=x
      b[n]=0
      ans+=(m-n)*x
  print(ans)
### BUGGY CODE ###

from bisect import bisect_left
from random import randint
D = int(input())
Cs = list(map(int, input().split()))
Sss = []
for _ in range(D):
    Ss = list(map(int, input().split()))
    Sss.append(Ss)

def change(d, afterIdx):
    global score
    i = d - 1
    beforeIdx = Ts[i] - 1
    afterIdx -= 1
    if beforeIdx == afterIdx:
        return

    newScore = score

    before = lasts[beforeIdx]
    # dが何番目にあるか
    k1 = bisect_left(before, d)
    w = before[k1+1] - d
    h = d - before[k1-1]
    newScore -= Sss[i][beforeIdx]
    newScore -= w * h * Cs[beforeIdx]

    after = lasts[afterIdx]
    # dが何番目にあるか
    k2 = bisect_left(after, d)
    w = after[k2] - d
    h = d - after[k2-1]
    newScore += Sss[i][afterIdx]
    newScore += w * h * Cs[afterIdx]

    if newScore > score:
        lasts[beforeIdx].pop(k1)
        lasts[afterIdx].insert(k2, d)
        Ts[i] = afterIdx + 1
        score = newScore

Ts = []
for _ in range(D):
    Ts.append(randint(1, 26))

score = 0
lasts = [[0] for _ in range(26)]
for i, t in enumerate(Ts):
    d = i + 1
    t -= 1
    score += Sss[i][t]
    lasts[t].append(d)
    for j in range(26):
        score -= (d - lasts[j][-1]) * Cs[j]

for i in range(26):
    lasts[i].append(D+1)


for i in range(5000000):
    change(randint(1, D), randint(1, 26))

for t in Ts:
    print(t)


### FIXED CODE ###

from bisect import bisect_left
from random import randint
D = int(input())
Cs = list(map(int, input().split()))
Sss = []
for _ in range(D):
    Ss = list(map(int, input().split()))
    Sss.append(Ss)

def change(d, afterIdx):
    global score
    i = d - 1
    beforeIdx = Ts[i] - 1
    afterIdx -= 1
    if beforeIdx == afterIdx:
        return

    newScore = score

    before = lasts[beforeIdx]
    # dが何番目にあるか
    k1 = bisect_left(before, d)
    w = before[k1+1] - d
    h = d - before[k1-1]
    newScore -= Sss[i][beforeIdx]
    newScore -= w * h * Cs[beforeIdx]

    after = lasts[afterIdx]
    # dが何番目にあるか
    k2 = bisect_left(after, d)
    w = after[k2] - d
    h = d - after[k2-1]
    newScore += Sss[i][afterIdx]
    newScore += w * h * Cs[afterIdx]

    if newScore > score:
        lasts[beforeIdx] = before[:k1] + before[k1+1:]
        lasts[afterIdx] = after[:k2] + [d] + after[k2:]
        Ts[i] = afterIdx + 1
        score = newScore

Ts = []
for _ in range(D):
    Ts.append(randint(1, 26))

score = 0
lasts = [[0] for _ in range(26)]
for i, t in enumerate(Ts):
    d = i + 1
    t -= 1
    score += Sss[i][t]
    lasts[t].append(d)
    for j in range(26):
        score -= (d - lasts[j][-1]) * Cs[j]

for i in range(26):
    lasts[i].append(D+1)


for i in range(100000):
    change(randint(1, D), randint(1, 26))

for t in Ts:
    print(t)
### BUGGY CODE ###

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

jun = True

for _ in range(Q):
    tmpS = S
    T = input().split()
    if T[0] == "1":
        jun = not jun

    if T[0] == "2" and ((T[1] == "1" and jun) or (T[1] == "2" and not jun)):
        S = T[2] + tmpS
        continue
        
    if T[0] == "2" and ((T[1] == "2" and jun) or (T[1] == "1" and not jun)):
        S = tmpS + T[2]

if jun:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

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

jun = True
head = ""

for _ in range(Q):
    T = input().split()
    if T[0] == "1":
        jun = not jun
    
    else:

        if (T[1] == "1" and jun) or (T[1] == "2" and not jun):
            head += T[2]
            continue

        else:
            S += T[2]

if jun:
    print(head[::-1] + S)
else:
    print(S[::-1] + head)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
if n % 2:
    if a.count(0) != 1:
        print(0)
        exit()
    for i in range(2, n, 2):
        if a.count(i) != 2:
            print(0)
            exit()
else:
    if a.count(1) != 2:
        print(0)
        exit()
    for i in range(1, n, 2):
        if i == 1:
            continue
        if a.count(i) != 2:
            print(0)
            exit()
mod = 10 ** 9 + 7
print((2 ** (n // 2)) % mod)

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
ac = collections.Counter(a)
if n % 2 == 1:
    for i in ac:
        if i == 0:
            if ac[i] != 1:
                print(0)
                exit()
        else:
            if ac[i] != 2:
                print(0)
                exit()
    print((2 ** (n // 2)) % (10 ** 9 + 7))
else:
    for i in ac:
        if i == 0:
            if ac[i] != 0:
                print(0)
                exit()
        else:
            if ac[i] != 2:
                print(0)
                exit()
    print((2 ** (n // 2)) % (10 ** 9 + 7))
### BUGGY CODE ###

n = int(input())
m = [0]
l = [n, 0, 0, 0, 0, 0]
ans = 0
for i in range(5):
    m.append(int(input()))
while l[5] < n:
    for i in range(4, -1, -1):
        if l[i] != 0:
            if l[i] <= m[i + 1]:
                l[i + 1] += l[i]
                l[i] = 0
            else:
                l[i + 1] += m[i + 1]
                l[i] -= m[i + 1]
    ans += 1
                
print(ans)

### FIXED CODE ###

n = int(input())
m = []
for i in range(5):
    m.append(int(input()))
ans = int(n / min(m))
if n % min(m) != 0:
    ans += 5
else:
    ans += 4
print(ans)
### BUGGY CODE ###

H,W = map(int,input().split())
A =[]
for i in range(H):
    A.append([1 if i == "#" else 0 for i in list(input())])
que = []
for i in range(H):
    for j in range(W):
        if A[i][j] == 1:
            que.append([i,j])
for ans in range(H+W):
    flag = 0
    tmp = []

    for _ in range(len(que)):
        i,j = que.pop()
        # 上
        if not i == 0:
            if A[i-1][j] == 0:
                A[i-1][j] = 1
                flag = 1
                tmp.append([i-1,j])
        # 下
        if not i == H-1:
            if A[i+1][j] == 0:
                A[i+1][j] = 1
                flag = 1
                tmp.append([i+1,j])
        # 左
        if not j == 0:
            if A[i][j-1] == 0:
                A[i][j-1] = 1
                flag = 1
                tmp.append([i,j-1])
        # 右
        if not j == W-1:
            if A[i][j+1] == 0:
                A[i][j+1] = 1
                flag = 1
                tmp.append([i,j+1])
    if flag == 0:
        break
    que = tmp.copy()
print(ans)

### FIXED CODE ###

import numpy as np
H,W = map(int,input().split())
A = []
for i in range(H):
    A.append([0 if i == "#" else H+W for i in list(input())])
A = np.array(A)
for i in range(H-1):
    A[i+1,:] = np.minimum(A[i,:]+1,A[i+1,:])
for i in range(H-1,0,-1):
    A[i-1,:] = np.minimum(A[i,:]+1,A[i-1,:])
for i in range(W-1):
    A[:,i+1] = np.minimum(A[:,i]+1,A[:,i+1])
for i in range(W-1,0,-1):
    A[:,i-1] = np.minimum(A[:,i]+1,A[:,i-1])
print(np.max(A))
### BUGGY CODE ###

import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
a = sorted(na())
k = 0

import heapq

for i in range(m):
    b,c = na()
    k += b
    for j in range(b):
        heapq.heappush(a, c)

for i in range(k):
    heapq.heappop(a)

print(sum(a))


### FIXED CODE ###

import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
a = na()

bc = [na() for i in range(m)]
bc.sort(key=lambda x:x[1])

for b,c in bc[::-1]:
  a.extend([c]*b)
  if len(a)>2*n:
    break

a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0, 0)]  # (time, silver, city, type)
visited = set()
fixed = 0
while q:
    t, s, v, z = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u, 0))

    if z == 1:
        continue

    ts = s
    tt = t
    c, d = exchanges[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v, 1))

print('\n'.join(map(str, ans[1:])))


### FIXED CODE ###

import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

print('\n'.join(map(str, ans[1:])))
### BUGGY CODE ###

import bisect

n = int(input())
As = list(map(int, input().split()))
As.sort()

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

cons = 10 ** 6
Ps = primes(cons)
Pset = set(Ps)
flags = [[0 for _ in range(n)] for _ in range(len(Ps))]
pairwiseFlag = True
setwiseFlag = True

# for p in Ps: # 素数
#   index = bisect.bisect_left(As, p)
#   temp = 0
#   for a in As[index:]:
#     if a in Pset:
#       temp += 1
#   if temp >= 2:
#     pairwiseFlag = False
#   if temp == n:
#     setwiseFlag = False
for ia, a in enumerate(As):
  index = bisect.bisect_right(Ps, a)
  temp = 0
  for ip, p in enumerate(Ps[:index]):
    if a % p == 0:
      flags[ip][ia] = 1
for i in range(len(Ps)):
  s = sum(flags[i])
  if s >= 2:
    pairwiseFlag = False
  if s == n:
    setwiseFlag = False

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')


### FIXED CODE ###

import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

# cons = 10 ** 6
# is_prime = [True] * (cons + 1)
# is_prime[0] = False
# is_prime[1] = False
# for i in range(2, int(cons**0.5) + 1):
#     if not is_prime[i]:
#         continue
#     for j in range(i * 2, cons + 1, i):
#         is_prime[j] = False
# Ps = [i for i in range(cons + 1) if is_prime[i]]
def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(int(n**0.5) + 1):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i, pi in enumerate(is_prime) if pi == 1]
Ps = eratosthenes(10 ** 6)

def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target |= primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

n,m = map(int,input().split())

a = int(m /n)
for i in range(a,0,-1):
  if m % i == 0:
    print(i)
    break

### FIXED CODE ###

n,m = map(int,input().split())

a = int(m /n)
for i in range(a,0,-1):
  if m % i == 0:
    print(i)
    break
### BUGGY CODE ###

import sys
 
sys.setrecursionlimit(200000000)
 
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]
 
l = [[] for i in range(n+1)]
for pi in ab:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
 
def dfs(graph, start, oya):
    if start != 1:
        graph[start].remove(oya)
    if len(graph[start]) == 0:
        return
    else:
        for i in graph[start]:
            dfs(graph, i, start)
 
dfs(l, 1, 1)
 
def dfs_2(graph, start, ans, x):
    ans[start] += x
    if len(graph[start]) == 0:
        return
    else:
        for i in graph[start]:
            dfs_2(graph, i, ans, x)
 
ans = [0 for i in range(n+1)]
for p, x in px:
    dfs_2(l, p, ans, x)
        
for i in range(1, n+1):
    print(ans[i], end=' ')
print()

### FIXED CODE ###

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]
 
l = [[] for i in range(n+1)]
for a, b in ab:  
    l[a].append(b)

value = [0 for i in range(n+1)]
for p, x in px:
    value[p] += x

stack = [1]
while stack:
    label = stack.pop()
    for i in l[label]:
        value[i] += value[label]
    stack += l[label]
        
print(*value[1:])
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
# sx, sy = map(int, input().split())
# gx, gy = map(int, input().split())
# sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
c = [input() for i in range(H)]
INF = 10**9
def bfs():
    dist = [[INF for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == INF:
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    return dist[gx][gy]

ans = -1
can = []
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                sx, sy = i, j
                gx, gy = k, l
                if c[sx][sy] == '#' or c[gx][gy] == '#':
                    continue
                can.append((sx, sy, gx, gy))

for sx, sy, gx, gy in can:
    if bfs() == INF:
        continue
    ans = max(ans, bfs())

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
c = [input() for i in range(H)]

INF = -1

def bfs():
    dist = [[INF for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        # if p[0] == gx and p[1] == gy:
        #     break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == INF:
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    ret = -1
    for i in range(H):
        ret = max(ret, max(dist[i]))
    return ret

ans = -1
for i in range(H):
    for j in range(W):
            sx, sy = i, j
            if c[sx][sy] == '#':
                continue
            ans = max(ans, bfs())
print(ans)