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

from copy import deepcopy
N, A = map(int, input().split())
x = list(map(int, input().split()))
dp = [[0] * (A*N+1) for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    _x = x[i]
    dpc = deepcopy(dp)
    for j in range(i+1):
        for a in range(A*N+1):
            if a >= _x:
                dp[j+1][a] += dpc[j][a-_x]
ans = 0
for i in range(1, N+1):
    ans += dp[i][i*A]
print(ans)


### FIXED CODE ###

from copy import deepcopy
N, A = map(int, input().split())
x = list(map(int, input().split()))
dp = [[0] * (A*N+1) for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    _x = x[i]
    dpc = deepcopy(dp)
    for j in range(i+1):
        for a in range(A*N+1):
            if a >= _x:
                dp[j+1][a] += dpc[j][a-_x]
ans = 0
for i in range(1, N+1):
    ans += dp[i][i*A]
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
imos=[0 for i in range(N+1)]
ANS=[str(N)]*N
if K>=50:
  ans=" ".join(ANS)
  print(ans)
else:
  for t in range(K):
    for i in range(N):
      l=max(0,i-A[i])
      r=min(N,i+A[i]+1)
      imos[l]+=1
      imos[r]-=1
    for i in range(0,N):
      imos[i+1]+=imos[i]
      A[i]=imos[i]
    imos=[0 for i in range(N+1)]
  for i in range(N):
    A[i]=str(A[i])
  ans=" ".join(A)
  print(ans)  
      

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
imos=[0 for i in range(N+1)]
ANS=[str(N)]*N
if K>=50:
  ans=" ".join(ANS)
  print(ans)
else:
  for t in range(K):
    for i in range(N):
      l=max(0,i-A[i])
      r=min(N,i+A[i]+1)
      imos[l]+=1
      imos[r]-=1
    for i in range(0,N):
      imos[i+1]+=imos[i]
      A[i]=imos[i]
    imos=[0 for i in range(N+1)]
  for i in range(N):
    A[i]=str(A[i])
  ans=" ".join(A)
  print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
C = []
ans = sum(A)


for i in range(M):
  b, c = map(int, input().split())
  for j in range(b):
    C.append(c)
C.sort(reverse=True)
if M > N:
  C = C[:N] #Aの数を超える分は不要

if A[0] >= C[0]:
    print(ans)
    exit()

k = len(C)
for i in range(len(C)):  
  if C[i] < A[i]:
    k = i
    break
ans = sum(C[:k]) + sum(A[k:])
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
  table.append((A[i],1))
for i in range(M):
  b,c = map(int, input().split())
  table.append((c,b))
table.sort()
count = 0
ans = 0
while True:
  c, b = table.pop()
  if b <= N - count:
    ans += c*b
    count += b
  else:
    ans += (N-count)*c
    break
print(ans)
### BUGGY CODE ###

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a2=[0]*(n+1)
for f in range(k):
    a1=a2[:]
    for x in range(n):
        y=max(0,x-a[x])
        a1[y]=a1[y]+1    
        z=min(n-1,x+a[x])
        a1[z+1]=a1[z+1]-1
    a[0]=a1[0]
    for x in range(1,n):    
        a[x]=a[x-1]+a1[x]
    if sum(a)==n**2:
        break
for i in range(n):
    print(a[i])

### FIXED CODE ###

from numba import njit

@njit(cache=True)
def aaa(n,k,a):
    for f in range(k):
        a1=[0]*(n+1)
        for x in range(n):
            y=max(0,x-a[x])
            a1[y]=a1[y]+1    
            z=min(n-1,x+a[x])
            a1[z+1]=a1[z+1]-1
        a[0]=a1[0]
        for x in range(1,n):    
            a[x]=a[x-1]+a1[x]
        if a==[n]*n:
            break
    return a

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]

b=aaa(n,k,a)
for i in range(n):
    print(b[i])
### BUGGY CODE ###

N, M = map(int, input().split())
shop = []
for _ in range(N):
    a, b = map(int, input().split())
    shop.append([a,b])
shop.sort()

cur = 0
cur_v = 0
for a, b in shop:
    for i in range(b):
        cur += 1
        cur_v += a
        if cur == M:
            print(cur_v)
            break

### FIXED CODE ###

N, M = map(int, input().split())
shop = []
for _ in range(N):
    a, b = map(int, input().split())
    shop.append([a,b])
shop.sort()

cur = 0
cur_v = 0
for a, b in shop:
    if cur + b > M:
        cur_v += (M - cur) * a
        break
    else:
        cur += b
        cur_v += a * b
print(cur_v)
### BUGGY CODE ###

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

Buka_list = []
for i in range(1,N+1,1):
    ninzu = A_list.count(i)
    Buka_list.append(ninzu)
    
for j in range(N):
    print(Buka_list[j])

### FIXED CODE ###

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

Buka_list = []

for i in range(N):
    Buka_list.append(0)
    
for j in A_list:
    Buka_list[j-1] += 1

for k in range(N):
    print(Buka_list[k])
### BUGGY CODE ###

K, S = map(int, input().split())
# print(K, S)

# 三重ループ？
# x,y,z の最大値はK

ans = 0
for i in range(K + 1):
    for j in range(K + 1):
        for k in range(K + 1):
            if i + j + k == S:
                ans += 1

print(ans)


### FIXED CODE ###

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

# a = []
ans = 0
for i in range(K + 1):
    for j in range(i + 1):
        k = S - i - j
        if k >= 0 and k <= j:
            # print(i, j, k)
            if i == j and j == k:
                ans += 1
            elif i == j or j == k:
                ans += 3
            else:
                ans += 6

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

N=int(input())
A=list(map(int,input().split()))
ans=sum(A)
s=N+1
j=s
sum_A=0

if A==sorted(A):
    print(0)
    exit()

for i in range(1,N):
    x=max(A[:s])
    s=A.index(x)
    A[s:j]=[x]*len(A[s:j])
    j=s
    if s==0:
        
        break
print(sum(A)-ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=sum(A)

for i in range(1,N):
    if A[i-1] > A[i]:
        A[i]=A[i-1]

print(sum(A)-ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
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)]

C = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])

V = [[2] * w for i in range(h)]
for i in range(h):
    V[i][0] -= 1
for i in range(w):
    V[0][i] -= 1

l = 6600
m = 0

M = [[[0] * l for i in range(w)] for j in range(h)]
N = [[0 for i in range(w)] for j in range(h)]
N[0][0] = C[0][0]

s = 0
Q = [[0, 0]]

M[0][0][C[0][0]] = 1
# M[0][0][m-C[0][0]] = 1

while len(Q) > s:
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        for ii in range(min(N[i][j]+1, l)):
            if M[i][j][ii] == 1:
                if abs(ii+C[i+1][j]) < l:
                    M[i+1][j][abs(ii+C[i+1][j])] = 1
                if abs(ii-C[i+1][j]) < l:
                    M[i+1][j][abs(ii-C[i+1][j])] = 1
        V[i+1][j] -= 1
        # print(N[i+1][j], N[i][j] + C[i+1][j])
        N[i+1][j] = max(N[i+1][j], N[i][j] + C[i+1][j])
        if V[i+1][j]==0:
            Q.append([i+1,j])
    if j+1 < w:
        for ii in range(min(N[i][j]+1, l)):
            if M[i][j][ii] == 1:
                if abs(ii+C[i][j+1]) < l:
                    M[i][j+1][abs(ii+C[i][j+1])] = 1
                if abs(ii-C[i][j+1]) < l:
                    M[i][j+1][abs(ii-C[i][j+1])] = 1
        V[i][j+1] -= 1
        N[i][j+1] = max(N[i][j+1], N[i][j] + C[i][j+1])
        if V[i][j+1]==0:
            Q.append([i,j+1])
        
    
    s += 1

# print(M[-1][-1])

ans = 10**5
for i in range(len(M[-1][-1])):
    if M[-1][-1][i] == 1:
        ans = i
        break
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
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)]
 
C = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])
 
M = [[0] * w for i in range(h)]
 
s = 0
Q = []
for i in range(h):
    Q.append([i, 0])
for i in range(1, w):
    Q.append([0, i])
for i in range(1, h):
    for j in range(1, w):
        Q.append([i, j])

m = 80
M[0][0] = (1 << m + C[0][0]) | (1 << m - C[0][0])

for s in range(len(Q)):
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        M[i+1][j] |= (M[i][j] << m + C[i+1][j]) | (M[i][j] << m - C[i+1][j])
    if j+1 < w:
        M[i][j+1] |= (M[i][j] << m + C[i][j+1]) | (M[i][j] << m - C[i][j+1])

        # N[i][j+1] = max(N[i][j+1], N[i][j] + C[i][j+1])
 
# print(M[-1][-1])
b = bin(M[-1][-1])
ans = float("inf")
for i in range(len(b)):
    if b[-1-i] == "1":
        ans = min(ans, abs(i - m*(h+w-1)))
print(ans)
### BUGGY CODE ###

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


MOD = 1000000007 

def pow(x, y):
    if y == 0:
        return 1
    ans = 1
    while y > 1:
        if y % 2 != 0:
            ans *= x
            ans %= MOD  
        x *= x
        x %= MOD 
        y //= 2
    return ans * x % MOD


def mod_inv(x):
  return pow(x, MOD - 2)

ans = 0
xCk_1 = {}
for i in range(k - 1, n):
  if i == k - 1:
    xCk_1[i] = 1
  else:
    xCk_1[i] = i * xCk_1[i - 1] * mod_inv(i - k + 1)

  ans += ((a[i] - a[n - i - 1]) % MOD) * xCk_1[i]
  ans %= MOD

print(ans)

### FIXED CODE ###

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


MOD = 1000000007 

def pow(x, y):
    if y == 0:
        return 1
    ans = 1
    while y > 1:
        if y % 2 != 0:
            ans *= x
            ans %= MOD  
        x *= x
        x %= MOD 
        y //= 2
    return ans * x % MOD


def mod_inv(x):
  return pow(x, MOD - 2)

ans = 0
xCk_1 = {}
for i in range(k - 1, n):
  if i == k - 1:
    xCk_1[i] = 1
  else:
    xCk_1[i] = (((i * xCk_1[i - 1]) % MOD) * mod_inv(i - k + 1)) % MOD

  ans += ((a[i] - a[n - i - 1]) % MOD) * xCk_1[i]
  ans %= MOD

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

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

ans = 1
for i in A:
    ans *= i
if 10 ** 18 < ans:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

def ans(a):
    ans = 1
    if 0 in a:
        return 0
    for i in A:
        ans *= i
        if 10 ** 18 < ans:
            ans = -1
            return ans
    return ans


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

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

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

for n in range(N):
    listA=list(map(int,input().split()))
    for i in range(listA[1]):
        l.append(int(listA[0]))

print(sorted(l)[K-1])

### FIXED CODE ###

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

c = 0
ans = 0
ab_list = list()

for n in range(N):
    a,b =list(map(int,input().split()))
    ab_list.append([a,b])

ab_list = sorted(ab_list, key=lambda x: x[0])

for a,b in ab_list:
    c += b
    if c >= K:
        ans = a    
        break

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

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

import sys

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=INT()

for h in range(1, 3501):
    for n in range(1, 3501):
        if 4*h*n-N*n-N*h==0: continue
        w=(N*h*n)/(4*h*n-N*n-N*h)
        if w>0 and w.is_integer():
            print(h, n, int(w))
            exit()


### FIXED CODE ###

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

import sys

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=INT()

for h in range(1, 3501):
    for n in range(1, 3501):
        if 4*h*n-N*n-N*h==0: continue
        w=(N*h*n)/(4*h*n-N*n-N*h)
        if w>0 and w.is_integer():
            print(h, n, int(w))
            exit()
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [0] + list(int(input()) for _ in range(q))
p = [k] * (n + 1)

def point_counter(x):
    return x - 1

for i in range(1, q + 1):
    p = list(map(point_counter, p))
    p[a[i]] += 1
    
for j in range(1, n + 1):
    if p[j] > 0:
        print('Yes')
    else:
        print('No')   

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [0] + list(int(input()) for _ in range(q))
p = [k - q] * (n + 1)

for i in range(1, q + 1):
    p[a[i]] += 1
    
for j in range(1, n + 1):
    if p[j] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
if a[0]==a[-1]:
  print(n)
else:
  for i in range(a[0],a[-1]):
    ans=max(ans,a.count(i)+a.count(i-1)+a.count(i+1))
  print(ans)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
c=collections.Counter(a)
ans=1
for i in range(min(a),max(a)+1):
  goukei=c[i-1]+c[i]+c[i+1]
  ans=max(ans,goukei)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
from itertools import accumulate

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

data = [[0]*500 for i in range(500)]
# data = [[0]*10 for i in range(10)]

for l, r in lr:
    data[l-1][r-1] += 1


for i in range(0, 500):
    data[i] = list(accumulate(data[i]))

# print(data)
for p, q in pq:
    ans = 0
    if p == 1:
        for i in range(p-1, q-1+1):
            ans += data[i][q-1]
    else:
        for i in range(p-1, q-1+1):
            ans += data[i][q-1]-data[i][p-1-1]
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
from itertools import accumulate
import numpy as np

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

data = [[0]*500 for i in range(500)]
# data = [[0]*10 for i in range(10)]

for l, r in lr:
    data[l-1][r-1] += 1


# for i in range(0, 500):
#     data[i] = list(accumulate(data[i]))

# print(data)
# for p, q in pq:
#     ans = 0
#     if p == 1:
#         for i in range(p-1, q-1+1):
#             ans += data[i][q-1]
#     else:
#         for i in range(p-1, q-1+1):
#             ans += data[i][q-1]-data[i][p-1-1]
#     print(ans)

data = np.array(data)

data = np.cumsum(data, axis=1)
data = np.cumsum(data, axis=0)

# print(data[:10, :10])
for p, q in pq:
    ans = 0
    if p == 1:
        ans = data[q-1][q-1]
    else:
        ans = data[q-1][q-1]-data[p-1-1][q-1]
    print(ans)
# for p, q in pq:
#     ans = 0
#     if p == 1:
#         for i in range(p-1, q-1+1):
#             ans += data[i][q-1]
#     else:
#         for i in range(p-1, q-1+1):
#             ans += data[i][q-1]-data[i][p-1-1]
#     print(ans)
### BUGGY CODE ###

from collections import defaultdict

N, K = map(int, input().split())
LRs = [tuple(map(int, input().split())) for _ in range(K)]
mod = 998244353

dd = defaultdict(int)
dd[N] = 1

for _i in range(N-1):
    i = N-1 - _i
    for l, r in LRs:
        for d in range(l, r+1):
            dd[i] = (dd[i] + dd[i+d]) % mod

print(dd[1])



### FIXED CODE ###

N, K = map(int, input().split())
LRs = [tuple(map(int, input().split())) for _ in range(K)]
mod = 998244353

def diff(l):
    tmp = None
    res = []
    for elm in l:
        if tmp is None:
            res.append(elm)
            tmp = elm
        else:
            res.append(elm-tmp)
            tmp = elm

    return res

res_diff = [0] * N
res_diff[1] = -1
res = [1]

for i in range(N-1):
    for l, r in LRs:
        if i+l < N:
            res_diff[i+l] += res[i]
        if i+r+1 < N:
            res_diff[i+r+1] -= res[i]
    
    res_next = (res[-1]+res_diff[i+1])%mod
    res.append(res_next)

print(res[N-1])
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()
S,T = LI()
S -= 1
T -= 1
routes = {}
for i in range(N):
    routes[i] = []
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = {}
for i in range(N):
    used[i] = -1

# print(routes)
def skip(now,move_cnt):
    flag = True
    if move_cnt % 3 == 0:
        if used[now] == -1:
            used[now] = move_cnt//3
        elif used[now] > move_cnt//3:
            used[now] = move_cnt//3
        else:
            flag = False
    if flag:
        for route in routes[now]:
            skip(route,move_cnt+1)

skip(S,0)
try:
    ans = used[T]
except:
    ans = -1
print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

from collections import deque

# q = queue.Queue()
q = deque()
q.append((S,0))
# Deep First Serch
while q:
    now, cost = q.popleft()
    for route in routes[now]:
        n_state = (cost + 1) % 3
        if used[route][n_state] == mod:
            used[route][n_state] = cost + 1
            q.append((route,cost+1))


# print(used)
try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
P = list(map(int, input().split()))

ans2 = list()
for i in range(n - (k-1)):
    ans2.append(P[i:i+k])
ans = 0
ans5 = list()

for i in ans2:
    ans = 0
    for j in i:
        ans += (1+j)/2
    ans5.append(ans)
print(max(ans5))


### FIXED CODE ###

from itertools import accumulate

n,k = map(int,input().split())
P = list(map(int,input().split()))

# 期待値の前計算
expP = [(P[i]+1)/2 for i in range(n)]

# 累積和の計算
acc = [0]+ list(accumulate(expP)) # 0を忘れずに

# 隣接する K 項の和の計算
ans = 0
for i in range(n-k+1):
  ans = max(ans,acc[i+k]-acc[i])
print(ans)
### BUGGY CODE ###

import heapq
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort()
queue = [0]*m
flag = 0
ans = 0
for i in range(1,m+1):
  for j in range(flag,n):
    if ab[j][0] > i:
      flag = j
      break
    queue.append(ab[j][1])
  k = heapq.nlargest(1,queue)
  ans += k[0]
  queue.remove(k[0])
print(ans)

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort()
queue = []
flag = 0
heapq.heapify(queue)
ans = 0
for i in range(1,m+1):
  for j in range(flag,n):
    if ab[j][0] <= i:
      heapq.heappush(queue,-ab[j][1])
      flag += 1
    else:
      break
  if queue != []:
    k = heapq.heappop(queue)
    ans += k
print(-ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
par = [-1 for _ in range(n)]

def dfs1(x, p):
	for v in adj[x]:
		if v != p:
			par[v] = x
			dfs1(v, x)
	return

dfs1(0, -1)

queries = [0 for _ in range(n)]
for _ in range(q):
	p, x = map(int, input().split())
	queries[p-1] += x

ans = [0 for _ in range(n)]

def dfs2(x, c):
	ans[x] = c + queries[x]
	for v in adj[x]:
		if v != par[x]:
			dfs2(v, ans[x])
	return

dfs2(0, 0)

print(*ans)

### FIXED CODE ###

import sys
#sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

queries = [0 for _ in range(n)]
for _ in range(q):
	p, x = map(int, input().split())
	queries[p-1] += x

ans = [0 for _ in range(n)]

st = [(0, 0, -1)]
while st:
	l = st.pop()
	ans[l[0]] = l[1] + queries[l[0]]
	for v in adj[l[0]]:
		if v != l[2]:
			st.append((v, ans[l[0]], l[0]))

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

import math

K = int(input())


def gcd3(a, b, c):
    d = math.gcd(a, b)
    e = math.gcd(d, c)
    return e


ans = 0
for x in range(1, K + 1, 1):
    for y in range(1, K + 1, 1):
        ans = ans + sum(list(map(lambda z: gcd3(x, y, z), range(1, K+1, 1))))

print(ans)


### FIXED CODE ###

import math

K = int(input())

ans = 0
for x in range(1, K + 1, 1):
    for y in range(1, K + 1, 1):
        ans = ans + sum(list(map(lambda z: math.gcd(math.gcd(x, y), z), range(1, K+1, 1))))

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

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

h_list = list(map(int,input().split()))

way_list = []
for i in range(m):
    org = list(map(int, input().split()))
    org.sort()
    way_list.append(org)

good = list(range(1,n+1,1))

for j in range(m):
    way = way_list[j]
    if h_list[way[0]-1] > h_list[way[1]-1]:
        if way[1] in good:
            good.remove(way[1])
    elif h_list[way[0]-1] < h_list[way[1]-1]:
        if way[0] in good:
            good.remove(way[0])
    else:
        if way[0] in good:
            good.remove(way[0])
        if way[1] in good:
            good.remove(way[1])

print(len(good))


### FIXED CODE ###

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

h_list = list(map(int,input().split()))

way_list = []
for i in range(m):
    org = list(map(int, input().split()))
    org.sort()
    way_list.append(org)

bad = []

for j in range(m):
    way = way_list[j]
    if h_list[way[0]-1] > h_list[way[1]-1]:
        bad.append(way[1])
    elif h_list[way[0]-1] < h_list[way[1]-1]:
        bad.append(way[0])
    else:
        bad.append(way[0])
        bad.append(way[1])

bad = list(set(bad))
print(n - len(bad))
### BUGGY CODE ###

n=int(input())
s=0
for i in range(n):
    s+=i
print(s)


### FIXED CODE ###

n=int(input())
s=n*(n-1)//2
print(s)
### BUGGY CODE ###

# dpぽい気がするのでそうする
# なぜかREなる....
# pythonだとrecursion limitがアレなのを忘れていた...

import sys

sys.setrecursionlimit(10 ** 8)


s = input()
dp = {}


def rec(i, cur_g, cur_p, tmp):
    if i in dp:
        return dp[i]
    if i == len(s):
        ret = 0
        for j in range(len(s)):
            if tmp[j] == "p" and s[j] == "g":
                ret += 1
            elif tmp[j] == "g" and s[j] == "p":
                ret -= 1
        return ret
    if cur_g > cur_p:
        # パーを出せる（出さなくてもいい）
        ret = max(
            rec(i + 1, cur_g, cur_p + 1, tmp + "p"),
            rec(i + 1, cur_g + 1, cur_p, tmp + "g"),
        )
        dp[i] = ret
        return ret

    else:
        # 勝てるかどうかにかかわらずグーを出すしか無い
        ret = rec(i + 1, cur_g + 1, cur_p, tmp + "g")
        dp[i] = ret
        return ret


print(rec(0, 0, 0, ""))


### FIXED CODE ###

# dpぽい気がするのでそうする
# なぜかREなる....
# pythonだとrecursion limitがアレなのを忘れていた...
# なぜかTLEなる....

import sys

sys.setrecursionlimit(10 ** 8)


s = input()
dp = {}


def rec(i, cur_g, cur_p, g, p):
    if i in dp:
        return dp[i]
    if i == len(s):
        ret = p - g
        dp[i] = ret
        return ret
    if cur_g > cur_p:
        # パーを出せる（出さなくてもいい）
        if s[i] == "g":
            ret = max(
                rec(i + 1, cur_g, cur_p + 1, g, p + 1),
                rec(i + 1, cur_g + 1, cur_p, g, p),
            )
            dp[i] = ret
            return ret
        elif s[i] == "p":
            ret = max(
                rec(i + 1, cur_g, cur_p + 1, g, p),
                rec(i + 1, cur_g + 1, cur_p, g + 1, p),
            )
            dp[i] = ret
            return ret
    else:
        # 勝てるかどうかにかかわらずグーを出すしか無い
        if s[i] == "g":
            ret = rec(i + 1, cur_g + 1, cur_p, g, p)
            dp[i] = ret
            return ret
        elif s[i] == "p":
            ret = rec(i + 1, cur_g + 1, cur_p, g + 1, p)
            dp[i] = ret
            return ret


print(rec(0, 0, 0, 0, 0))