Harryxun/stf_run huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
int main() {
  int n, m;
  long long ans = 0;
  cin >> n >> m;
  vector<int> a(n), b(n);
  vector<pair<int, int> > ab(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
  }
  for(int i = 0; i < n; i++) {
    ab[i] = make_pair(a[i], b[i]);
  }
  sort(ab.begin(), ab.end());  
  for(int i = 0; i < n; i++) {
    int buy = min(m, ab[i].second);
    ans += buy * ab[i].first;
    m -= buy;
  }
  
  cout << ans << endl;
}

### FIXED CODE ###

import numpy as np
n, m = map(int, input().split())
a = []
b = []
bot = m
ans = 0
for i in range(n):
  l,m = map(int, input().split())
  a.append(l)
  b.append(m)
  
a = np.array(a)
b = np.array(b)
s = np.argsort(a)
for i in s:
  if(bot >= b[i]):
    bot -= b[i]
    ans += a[i] * b[i]
  else: 
    ans += a[i] * (bot)
    bot = 0
    break

print(ans)
def solve(a,b):
  def needTaps(a,b,holes=1,res=0):
    if holes >= b:
      return res
    elif:
      return needTaps(a,b,holes+a-1,res+1)
    
  return needTaps(a,b)

a,b=map(int,input().split())
print(solve(a,b))


### FIXED CODE ###

a, b = map(int,input().split())

i = 0
while True:
  if a + (i-1)*(a-1) >= b:
    ans = i
    break
  i += 1

print(ans)
n=int(input())
count=0
v=[]
v=[int(i) for i in input().split()]
for i in range(n-2):
    if v[i]==v[i+2]:
        pass
    else:
        count+=1
v.pop(v[0])
if len(v)==0:
    if n%2==0:
        count=int(n/2)
    else:
        count=int((n-1)/2)
print(count)


### FIXED CODE ###

import itertools
from collections import Counter


n = int(input())
v = list(map(int, input().split()))
ev_cnt = Counter(v[::2])
od_cnt = Counter(v[1::2])
ev_cnt[-1] = 0
od_cnt[-2] = 0
ev = ev_cnt.most_common(2)
od = od_cnt.most_common(2)
ans = n
for (k1, v1), (k2, v2) in itertools.product(ev, od):
    if k1 == k2:
        continue
    x = (n - v1 - v2)
    ans = min(ans, x)
print(ans)
X, Y, A, B, C = map(int, input().split())
P = sorted(list(map(int, input().split())), reverse=True)
Q = sorted(list(map(int, input().split())), reverse=True)
R = sorted(list(map(int, input().split())), reverse=True)

red = sorted(P[:X])
gre = sorted(Q[:Y])
ans = sum(red) + sum(gre) 
j, k = 0, 0

for i in range(X+Y):
    if(red[j] <= gre[k]):
        if R[i] > red[j] :
            ans = ans - red[j] + R[i]
            j += 1
        else:
            break
    else:
        if R[i] > gre[k] :
            ans = ans - gre[k] + R[i]
            k += 1
        else:
            break
print(ans)

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
P = sorted(list(map(int, input().split())), reverse=True)
Q = sorted(list(map(int, input().split())), reverse=True)
R = sorted(list(map(int, input().split())), reverse=True)

red = sorted(P[:X])
gre = sorted(Q[:Y])
m = min((X+Y),C)
n = R[:m]
red.extend(gre)
red.extend(n)
red = sorted(red, reverse=True)

print(sum(red[:X+Y]))
n = int(input())
s = input()
k = int(input())
for i in s:
    if i == s[k]:
        print(i, end="")
    else:
        print("*", end="")

### FIXED CODE ###

n = int(input())
s = input()
k = int(input())
for i in s:
    if i == s[k-1]:
        print(i, end="")
    else:
        print("*", end="")
# -*- coding: utf-8 -*-

import sys


lineNumber = 0
#for line in [ "2", "1000", "800", "99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999", "1" ]:
for line in sys.stdin.readlines():
    lineNumber += 1

    # line exception
    if lineNumber == 1:
        [a, b] = [0, 0]
        continue
    
    # get data
    List = map(int, line.strip().split())

    # set data
    if lineNumber % 2 == 0: a = List[0]
    else                  : b = List[0]

    # sum
    if lineNumber % 2 == 1:
        c = a + b
        if c < 10**79: print str(c)
        else         : print "overflow"

### FIXED CODE ###

for i in range(int(raw_input())):
    x = int(raw_input())
    y = int(raw_input())
    s = str(x+y)
    if len(s) > 80:
        print "overflow"
    else :
        print s
import numpy as np
N, P = map(int,input().split())
S = list(map(int,input()))

ans = 0
if P == 2:
    for i,s in enumerate(S):
        if s % 2 == 0:
            ans += i + 1
elif P == 5:
    for i,s in enumerate(S):
        if s % 5 == 0:
            ans += i + 1
else:
    res = []
    n = 0
    for s in S[::-1]:
        n = (10*n + s) % P
        res.append(n)

    res.append(0) # right

    inds, cnts = np.unique(res, return_counts=True)

    for cnt in cnts:
        if cnt == 1:
            continue
        ans += cnt * (cnt - 1) // 2
print(ans)

    



### FIXED CODE ###

from collections import Counter
N, P = map(int,input().split())
S = input()

'''
N, P  = 10, 7
S = '1234567890'
tans = 0
for i in range(N):
    for j in range(i+1,N+1):
        t = int(S[i:j])
        tans += ((t % P) == 0)
print(tans)
'''

S = list(map(int,S))

ans = 0
if P == 2:
    for i,s in enumerate(S):
        if s % 2 == 0:
            ans += i + 1
elif P == 5:
    for i,s in enumerate(S):
        if s % 5 == 0:
            ans += i + 1
else:
    res = []
    n = 0
    k = 1
    for s in S[::-1]:
        n = (s * k + n) % P
        k = (k * 10) % P
        res.append(n)

    res.append(0) # right
    #print(N,P,S)
    #print(res)

    cnts = Counter(res)
    for ind, cnt in cnts.items():
        if cnt == 1:
            continue
        ans += cnt * (cnt - 1) // 2

print(ans)
import numpy as np
from sys import stdin
ans=0
c=0
N = int(input().rstrip())
for i in range(N):
  c=0
  i+=1
  if i%2==1:
    for j in range(i):
      j+=1
      if i%j==0:
        c+=1
  if c==8:
    ans+=1

print(ans)

### FIXED CODE ###

import numpy as np
from sys import stdin
ans=0
c=0
N = int(input().rstrip())
for i in range(N):
  c=0
  i+=1
  if i%2==1:
    for j in range(i):
      j+=1
      if i%j==0:
        c+=1
  if c==8:
    ans+=1

print(ans)
H, W = map(int(input().split()))

while True:
    if (H + W == 0) : break
    
    for i in range(0, H-1):
        print('#' * W)



### FIXED CODE ###

while True:
    H, W = map(int, input().split())

    if (H + W == 0) : break
    
    for i in range(H):
        print('#' * W)

    print()
import numpy as np

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

X = []
for i in range(N):
    x = [0 for _ in range(N)]
    for j in range(i, i+2):
        if j >= N:
            continue
        x[j] = 1
    if i == N - 1:
        x[0] = 1
    X.append(x)

Y = A
X = np.matrix(X)
Y = np.matrix(Y).reshape(-1, 1)
ans = np.linalg.solve(X,Y) * 2
ans = list(map(lambda x: str(int(x)), ans))
print(' '.join(ans).strip())


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
X = []
for i in range(N):
    X.append(sum(A) - 2 * sum([x for j, x in enumerate(A) if j % 2 != 0]) if i == 0 else 2 * A[i-1] - X[i-1])
print(' '.join(list(map(str, X))).strip())
N = input()
S = str(input())

if N + 2 // 2 == 1:
  print('No')

else:
  f = int(N/2)
  b = int(N/2)
  front = S[:f]
  back = S[b:]
  if front == back:
    print('Yes')
  else:
    print('No')
    

### FIXED CODE ###

N = int(input())
S = str(input())
 
if N + 2 // 2 == 1:
    print('No')
 
else:
    f = int(N/2)
    b = int(N/2)
    front = S[:f]
    back = S[b:]
    if front == back:
        print('Yes')
    else:
        print('No')
    
#print(front)
#print(back)
import sys
def solve(stns, idx, mem):

    if idx >= len(stns) -1:
        return 0

    if idx in mem: 
        return mem[idx]

    if idx == len(stns) - 2: 
        # can take only one step
        # print(idx)  
        # final_step = solve(stns, idx + 1, mem) + abs(stns[idx] - stns[idx+1])
        final_step = abs(stns[idx] - stns[idx+1])
        mem[idx] = final_step
        return final_step
    else: 
        # step: i + 11
        step1 = solve(stns, idx + 1, mem) + abs(stns[idx] - stns[idx+1])
        # step: i + 2
        step2 = solve(stns, idx + 2, mem) + abs(stns[idx] - stns[idx+2])

        min_cost = min(step1, step2)
        mem[idx] = min_cost 

        return min_cost



def take_input():
    n = input().strip()
    stns = [int(x) for x in input().strip().split()]



    # reader = (s.rstrip() for s in sys.stdin)
    # input = reader.__next__
    # sys.setrecursionlimit(1000000)
    # do magic here
    # n = int(input())
    # stns = [int(x) for x in input().split()]
    mem = {}
    res = solve(stns, 0, mem)
    print(res)

take_input()

### FIXED CODE ###

import sys
def solve(stns, idx, mem):

    if idx >= len(stns) -1:
        return 0

    if idx in mem: 
        return mem[idx]

    if idx == len(stns) - 2: 
        # can take only one step
        # print(idx)  
        # final_step = solve(stns, idx + 1, mem) + abs(stns[idx] - stns[idx+1])
        final_step = abs(stns[idx] - stns[idx+1])
        mem[idx] = final_step
        return final_step
    else: 
        # step: i + 11
        step1 = solve(stns, idx + 1, mem) + abs(stns[idx] - stns[idx+1])
        # step: i + 2
        step2 = solve(stns, idx + 2, mem) + abs(stns[idx] - stns[idx+2])

        min_cost = min(step1, step2)
        mem[idx] = min_cost 

        return min_cost



def take_input():
    # n = input()
    # stns = [int(x) for x in input().split(' ')]



    reader = (s.rstrip() for s in sys.stdin)
    input = reader.__next__
    sys.setrecursionlimit(1000000)
    # do magic here
    n = int(input())
    stns = [int(x) for x in input().split()]
    mem = {}
    res = solve(stns, 0, mem)
    print(res)

take_input()
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

def main():

  n,m=map(int,input().split())
  d=[[0 for i in range(n)] for i in range(n)]
  to=[[] for i in range(n)]
  for i in range(m):
    u,v=map(lambda x:int(x)-1,input().split())
    to[u].append(v)
  s,t=map(lambda x:int(x)-1,input().split())

  #print(to)

  # calc d (after 3 times dist)
  for i in range(n):
    first,second,third=[],[],[]
    for j in to[i]:
      first.append(j)
    for j in first:
      for k in to[j]:
        second.append(k)
    for j in second:
      for k in to[j]:
        third.append(k)
        d[i][k]=1

  ans=dijkstra(csr_matrix(d),indices=0).astype(int)
  print(ans[t] if ans[t]>0 else -1)


if __name__=='__main__':
  main()

### FIXED CODE ###

from collections import deque

def main():

  n,m=map(int,input().split())
  INF=10**9
  d=[[INF]*3 for i in range(n)]
  to=[[] for i in range(n)]
  for i in range(m):
    u,v=map(lambda x:int(x)-1,input().split())
    to[u].append(v)
  s,t=map(lambda x:int(x)-1,input().split())

  #print(to)
  # calc d (after 3 times dist)
  d[s][0]=0
  cnt=0
  q=deque([(s,cnt)])
  while q:
    u,c=q.popleft()
    for v in to[u]:
      nc=(c+1)%3
      if d[v][nc]!=INF: continue;
      d[v][nc]=d[u][c]+1
      q.append((v,nc))
      
  #print(d)
  ans=d[t][0]
  print(ans//3 if ans!=INF else -1)

  
if __name__=='__main__':
  main()
a, b = map(int, input().split())
if (a * b) % == 1:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a, b = map(int, input().split())
if (a * b) % 2 == 1:
  print('Yes')
else:
  print('No')
def resolve():
    N, K = map(int, input().split())
    R, S, P = map(int, input().split())
    T = list(input())

    score = {'r':  P, 's': R, 'p': S}

    ans = 0
    for i in range(K):
        ans += score[T[i]]

    for i in range(K, N):
        if T[i-K] == T[i]:
            T[i] = ' '
            continue
        ans += score[T[i]]

    print(s)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    N, K = map(int, input().split())
    R, S, P = map(int, input().split())
    T = list(input())

    score = {'r':  P, 's': R, 'p': S}

    ans = 0
    for i in range(K):
        ans += score[T[i]]

    for i in range(K, N):
        if T[i-K] == T[i]:
            T[i] = ' '
            continue
        ans += score[T[i]]

    print(ans)

if __name__ == "__main__":
    resolve()
A, B, C, D = list(map(int, list(input().strip())))

for op1 in [-1, 1]:
    for op2 in [-1, 1]:
        for op3 in [-1, 1]:
            if A + (op1 * B) + (op2 * C) + (op3 * D) == 7:
                print(f'{A}{"+" if op1 == 1 else "-"}{B}{"+" if op2 == 1 else "-"}{C}{"+" if op3 == 1 else "-"}{D}=7')
                exit()

### FIXED CODE ###

A, B, C, D = list(map(int, list(input().strip())))

for op1 in [-1, 1]:
    for op2 in [-1, 1]:
        for op3 in [-1, 1]:
            if A + (op1 * B) + (op2 * C) + (op3 * D) == 7:
                print('{}{}{}{}{}{}{}=7'.format(A, "+" if op1 == 1 else "-", B, "+" if op2 == 1 else "-", C, "+" if op3 == 1 else "-", D))
                exit()
sardine

### FIXED CODE ###

s = input()
length = len(s)

ans = ''

for i in range(length):
    ans += 'x'

print(ans)
s = list(input())

q = int(input())

reverse = 0

for i in range(q):
  query = list(input().split())
  if query[0] == '1':
    reverse ^= 1
    continue
  else:
    if query[1] == '1':
      if reverse:
        s.append(query[2])
      else:
        s.appendleft(query[2])
    else:
      if reverse:
        s.appendleft(query[2])
      else:
        s.append(query[2])
if reverse:
  s = s[::-1]
print(''.join(s))


### FIXED CODE ###

from collections import deque

s = deque(list(input()))

q = int(input())

reverse = 0

for i in range(q):
  query = list(input().split())
  if query[0] == '1':
    reverse ^= 1
    continue
  else:
    if query[1] == '1':
      if reverse:
        s.append(query[2])
      else:
        s.appendleft(query[2])
    else:
      if reverse:
        s.appendleft(query[2])
      else:
        s.append(query[2])
if reverse:
  print(''.join(s)[::-1])
else:
  print(''.join(s))
print(N*(100**D)) if N!=100 else print(101*(100**D))

### FIXED CODE ###

D,N= (int(i) for i in input().split())
print(N*(100**D)) if N!=100 else print(101*(100**D))
s=input()
n=int(input())
front=""
back=""
reverse=False

for i in range(n):
  t=input().split()
  if t[0]=="1":
    reverse=not reverse
  else:
    if (t[1]=="1")and not reverse:
      front=front+t[2]
    elif (t[1]=="2")and reverse:
    else:
      back=back+t[2]
if reverse:
  print(back[::-1]+s+front)
else:
  print(front[::-1]+s+back)


### FIXED CODE ###

S = input()
Q = int(input())
reverse = False
front = ""
end = S

for _ in range(Q):
    I = input().split()
    if I[0] == "1":
        reverse = not reverse
    else:
        if (I[1] == "1") ^ reverse:
            front =front + I[2]
        else:
            end = end + I[2]


if reverse:
    print(end[::-1]+front)
    #print("".join(list(reversed(end)))+front)
else:
    print(front[::-1]+end)
    #print("".join(list(reversed(front)))+end)
dish = [int(input()) for d in range(5)]
diff = 0
ans = []
for index,d in enumerate(dish):
  if d % 10 == 0:
    ans.append(d)
  else:
    d10 = ((d //10) +1) * 10
    ans.append(d10)
    tmp = d10-d
    if diff < tmp:
      diff = tmp
      last= index
    
del ans[last]
print(sum(ans)+dish[last])



### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
dish = [a,b,c,d,e]
last = 0
for index,d in enumerate(dish):
  if d % 10 != 0:
    d10 = ((d // 10)+1) *10
    if last <= d10 - d:
      last = d10 - d
    dish[index] = d10
print(sum(dish)-last)
# -*- coding: utf-8 -*-
import math
import sys

X = int(input())

for A in range(-118, 190):
  for B in range(-119, 119):
    val = math.pow(A, 5) - math.pow(B, 5)
    if(val == X):
      print(A, B)
      sys.exit(0)
~                        

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
import sys

X = int(input())

for A in range(-118, 120):
  for B in range(-119, 119):
    val = math.pow(A, 5) - math.pow(B, 5)
    if(val == X):
      print(A, B)
      sys.exit()
h , w = map(int,input().split())
lis = []
for i in range(w):
    lis.append(input())
print('#'*(w+2))
for i in range(h):
    print('#'+lis[i]+'#')
print('#'*(w+2))

### FIXED CODE ###

h , w = map(int,input().split())
lis = []
for i in range(h):
    lis.append(input())
print('#'*(w+2))
for i in range(h):
    print('#'+lis[i]+'#')
print('#'*(w+2))
a, b = map(int, input().split())
print(a - (2 * b) if a > 2b else 0)

### FIXED CODE ###

a, b = map(int, input().split())
print(a - (2 * b) if a > (2 * b) else 0)
s = input()
k = int(input())
for i,j in enumerate(s):
  if j == "1"
    if (i+1) == k:
      print(j)
      break
  else:
    print(j)
    break

### FIXED CODE ###

s = input()
k = int(input())
for i,j in enumerate(s):
  if j == "1":
    if (i+1) == k:
      print("1")
      break
  else:
    print(j)
    break
N , M = (map(int , input().split()))
X = list(map(int , input().split()))
sorted_x = sorted(X)
ans= 0
total_kukann = 0
kukann_kyori = []
a = N-1
for i in range(len(sorted_x)-1):
    kukann_kyori.append(sorted_x[i + 1] - sorted_x[i])
    total_kukann += sorted_x[i + 1] - sorted_x[i]
kukann_kyori.sort()
for j in range(1,a+1):
    total_kukann -= kukann_kyori[-j]
if N >= M:
    total_kukann = 0
print(total_kukann)

### FIXED CODE ###

N , M = (map(int , input().split()))
X = list(map(int , input().split()))
sorted_x = sorted(X)
total_kukann = 0
kukann_kyori = []
a = N-1
for i in range(len(sorted_x)-1):
    kukann_kyori.append(sorted_x[i + 1] - sorted_x[i])
    total_kukann += sorted_x[i + 1] - sorted_x[i]
kukann_kyori.sort()
if N >= M:
    total_kukann = 0
else:
    for j in range(1,a+1):
        total_kukann -= kukann_kyori[-j]
print(total_kukann)
n=int(input())
a,c,e,f=[],[],0,0
for i in range(n):
    a.append(int(input()))
    b=[]
    for i in range(a[-1]):
        b.append(list(map(int,input().split())))
    c.append(b)
for i in range(2**n):
    d=bin(i)[2:-1]+bin(i)[-1]
    d='0'*(n-len(d))+d
    for j in range(n):
        if d[j]==1:
            e+=1
    for j in range(n):
        if d[j]==0:
            continue
        for k in range(a[j]):
            if d[c[j][k][0]]!=c[j][k][1]:
                g=True
                continue
    if g:
        continue
    f=max(e,f)
print(f)

### FIXED CODE ###

n=int(input())
s=[]
ans=0
for i in range(n):
    a=int(input())
    s.append([list(map(int,input().split())) for _ in range(a)])
for i in range(2**n):
    bit=bin(i)[2:].zfill(n)
    flag=1
    for j in range(n):
        if bit[j]=='0':
            continue
        for sh in s[j]:
            if int(bit[sh[0]-1])!=sh[1]:
                flag=0
    if flag:
        ans=max(ans,bit.count('1'))
print(ans)
import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a)

cs_plus = np.cumsum((a > 0) * a)
cs_plus = [0] + list(cs_plus)
plus = [v2 - v1 for v1, v2 in zip(cs_plus[:-k], cs_plus[k:])]

cs_minus = np.cumsum((a < 0) * a)
cs_minus = [0] + list(cs_minus)
minus = [v2 - v1 for v1, v2 in zip(cs_minus[:-k], cs_minus[k:])]

print(cs_plus[-1] - min(min(plus), -max(minus)))


### FIXED CODE ###

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

diff = abs(y) - abs(x)

if y == 0:
    if x <= 0:
        print(-x)
        exit()
    if x >= 0:
        print(x + 1)
        exit()

result = 0
if (x >= 0) == (y >= 0):
    if x < 0 and diff > 0:
        result = 2
    if x >= 0 and diff < 0:
        result = 2
else:
    result = 1
if diff < 0:
    diff *= -1
print(result + diff)
_ = input()
card_list = sorted(input().split())[::-1]
print(sum(card_list[::2])-sum(card_list[1::2]))

### FIXED CODE ###

_ = input()
card_list = sorted(map(int, input().split()))[::-1]
print(sum(card_list[::2])-sum(card_list[1::2]))
import numpy as np
from math import gcd

N=int(input())
A=list(map(int, input().split()))
A=np.array(A)
mod=10**9+7
def lcm(a,b):
    return a//gcd(a,b)*b

LCM=1
for x in A:
    LCM=lcm(LCM,x)



#print(LCM)
print(int((LCM//A).sum()%mod))

### FIXED CODE ###


#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
if N==1:
  print(1)
  exit()

mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return a//gcd(a,b)*b

if N==2:
  LCM=lcm(A[0],A[1])
  ans=((LCM//A[0])+(LCM//A[1]))%mod
  print(ans)
  exit()

LCM=1
#LCM%=mod
for a in A:
  LCM=lcm(LCM, a)
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  #ans%=mod

print(int(ans%mod))
X = int(input())

item_list = [100, 101, 102, 103, 104, 105]

pre_list = []
sum_value = 0
for i in range(1, 1001):
    tmp_list = []
    for value in item_list:
        tmp_list.append(i * value)
    
    pre_list.append(tmp_list)

sum_list = [[0] * 7 for i in range(1001)]
for i in range(1000):
    for j in range(6):
            sum_list[i + 1][j + 1] = sum_list[i][j + 1] + sum_list[i + 1][j] - sum_list[i][j] + pre_list[i][j]

flag = 0
for i1 in range(0, 1000):
    for i2 in range(i1+1, 1001):
        for j1 in range(0, 6):
            for j2 in range(j1+1, 7):
                    value = sum_list[i2][j2] - sum_list[i1][j2] - sum_list[i2][j1] + sum_list[i1][j1]  
                if X == value:
                    flag = 1

print(flag)

### FIXED CODE ###

X = int(input())

item_value = [100, 101, 102, 103, 104, 105]
dp = [0] * (100001)
for value in item_value:
    dp[value] = 1

for i in range(200, X + 1):
    for value in item_value:
        if dp[i - value] == 1:
            dp[i] = 1

print(dp[X])
#-*- coding: utf-8
#  -*-
"""
oj dl https://atcoder.jp/contests/abc116/tasks/abc116_d -d test-d
oj test -d test-d -c "python abc116d.py"
oj test -d test-d -c "python abc116d.py" test-d/sample-3.in
"""
from collections import defaultdict
import sys
import math
from datetime import datetime
from typing import List


class TreeNode:
    def __init__(self):
        self.val = 0
        self.vertex = []

def make_trees(n, A, B):
    trees = []
    for i in range(n):
        trees.append(TreeNode())
    for i in range(len(A)):
        a = A[i]-1
        b = B[i]-1
        trees[a].vertex.append(b)
    return trees

def dfs(node: TreeNode, x: int, trees):
    if node:
        node.val += x
        for i in node.vertex:
            dfs(trees[i], x, trees)


def sol(n, q, A, B, P, X):
    trees = make_trees(n, A, B)
    for i in range(len(P)):
        p = P[i]-1
        x = X[i]
        t = trees[p]
        # dfs, give point x
        dfs(t, x, trees)
    #
    return [t.val  for t in trees]
    #return n, q, A, B, P, X



do_submit = True
#do_submit = False

def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    print(parsed_lines)
    n = int(parsed_lines[0][0])
    q = int(parsed_lines[0][1])
    A = []
    B = []
    P = []
    X = []
    for i in range(1, n-1+1):
        a = int(parsed_lines[i][0])
        b = int(parsed_lines[i][1])
        A.append(a)
        B.append(b)
    for i in range(n, 1+n+q-1):
        p = int(parsed_lines[i][0])
        x = int(parsed_lines[i][1])
        P.append(p)
        X.append(x)

    # S = parsed_lines[1][0]
    # return n, k, S
    return n, q, A, B, P, X


if not do_submit:
    n, q, A, B, P, X = input_parse("""
    4 3
    1 2
    2 3
    2 4
    2 10
    1 100
    3 1
    """)
    print(sol(n, q, A, B, P, X))

else:
    # n = int(input().strip())
    # q = int(input().strip())
    n, q = list(map(int, input().split()))
    A = []
    B = []
    P = []
    X = []
    for i in range(n-1):
        a, b = list(map(int, input().split()))
        # a = int(input().strip())
        # b = int(input().strip())
        A.append(a)
        B.append(b)
    for i in range(q):
        p, x = list(map(int, input().split()))
        # p = int(input().strip())
        # x = int(input().strip())
        P.append(p)
        X.append(x)
    print(sol(n, q, A, B, P, X))



### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
 
ki = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ki[a].append(b)
    ki[b].append(a)
# print(ki)
 
cnt = [0] * (n + 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x
 
 
# print(cnt)
 
 
def d(y, parent):
    for i in ki[y]:
        if i == parent:
            continue
        cnt[i] += cnt[y]
        d(i, y)
 
 
d(1, -1)
print(*cnt[1:])