Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()

arr=sorted(limii())

mat=[]
for i in range(m):
    b,c=mii()
    mat.append([b,c])

mat.sort(key=lambda x: x[1],reverse=True)
maxboundary=mat[0][1]
ans=0
i=0
temp=0
while maxboundary>arr[temp] and temp<n and i<m:
    ans+=mat[i][1]
    temp+=1
    mat[i][0]-=1
    if mat[i][0]==0:
        i+=1
        maxboundary=mat[i][1]
    #print(ans,temp,i,mat,maxboundary)

print(ans+sum(arr[temp:]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()

arr=sorted(limii())

mat=[]
for i in range(m):
    b,c=mii()
    mat.append([b,c])

mat.sort(key=lambda x: x[1],reverse=True)
maxboundary=mat[0][1]
ans=0
i=0
temp=0
while maxboundary>arr[temp] and temp<n and i<m:
    ans+=mat[i][1]
    
    temp+=1
    if temp==n:
        break
    mat[i][0]-=1
    if mat[i][0]==0:
        i+=1
        if i<m:
            maxboundary=mat[i][1]
    #print(ans,temp,i,mat,maxboundary)

print(ans+sum(arr[temp:]))
r = int(input())

m = 3.141592 * r * r
l = 3.141592 * r * 2

print("{:.5f}".format(m),"{:.5f}".format(l)) 




### FIXED CODE ###

r = float(input())

#円の面積 = πr^2
#円周の長さ=直径*π=2πr
#print(c,d,"{:.5f}".format(e)) 

m = 3.141592653589 * r * r
l = 3.141592653589 * r * 2

print("{:.6f}".format(m),"{:.6f}".format(l))
n = int(input())
t, a = map(int, input().split())
lis = list(map(int, input().split()))

avg_tmp = abs(t - (lis[0] * 0.006) - a)
c = 0
for i in range(1, n):
    min_diff = abs(t - (lis[i] * 0.006) - a)
    if(avg_tmp > min_diff):
        l = i
print(l+1)

### FIXED CODE ###

n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))
L = []

for i in range(n):
    L.append(abs(a - (t - h[i] * 0.006)))
print(L.index(min(L)) + 1)
N = int(input())
A_list = []
B_list = []
count = 0
D = 0
for i in range(N):
  A,B = map(int, input().split())
  A_list.append(A)
  B_list.append(B)
c = zip(A, B)
c.sort(key = itemgetter(1))
A, B = zip(*c)
for o in range(N):
  count += A[i]
  if count > B[i]:
    print("No")
    D = 1
    break
if D== 0:
  print("Yes")
  
  
  

### FIXED CODE ###


N = int(input())
count = 0
D = 0
task = [list(map(int, input().split())) for _ in range(N)]
task = sorted(task, key = lambda x:x[1])
for i in range(N):
  count += task[i][0]
  if count > task[i][1]:
    print("No")
    D = 1
    break
if D== 0:
  print("Yes")
a,b = map (int, raw_input().split())
if a > b
print "a > b"
if a < b
print "a < b"
if a == b
print "a=b"

### FIXED CODE ###

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

if a < b:
    print ("a < b")
elif a > b:
    print ("a > b")
elif a == b:
    print ("a == b")
n = int(input())
alist=list(map(int,input().split()))
core = 0
for i in range(n-3):
  core +=min(alist[i],alist[i+1],alist[i+2])
min1 = min(alist[0],alist[1])
min2 = min(alist[-2],alist[-1])
print(core + min1 + min2 + alist[-1])

### FIXED CODE ###

n = int(input())
alist=list(map(int,input().split()))
alist.insert(0,1e7)
alist.append(1e7)
core = 0
for i in range(n):
  core +=min(alist[i],alist[i+1])
print(core)
n=int(input())
a=map(int,input().split())
loop=True
cnt=0
while loop:
    for i in range(n):
        if a[i]%2==0:
            a[i]=a[i]/2
        else:
          loop=False
          break
    cnt=cnt+1
print(cnt)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
loop=True
cnt=0
while loop:
    for i in range(n):
        if a[i]%2==0:
            a[i]=a[i]/2
        else:
          loop=False
          break
    cnt=cnt+1
print(cnt-1)
import math
N=input()
x=[]
y=[]
M=0
for i in N:
    F=input()
    v,s=list(map(int,F.split(' ')))
    x.append(v)
    y.append(s)
def dis(x,y,x2,y2):
    return math.sqrt((x-x2)**2+(y-y2)**2)
for i in N:
    for j in N:
        M=M+dis(x[i],y[i],x[j],y[j])
print(M/math.factorial(N))

### FIXED CODE ###

import math
N=int(input())
x=[]
y=[]
M=0
for i in range(0,N):
    F=input()
    [v,s]=list(map(int,F.split(' ')))
    x.append(v)
    y.append(s)
def dis(x,y,x2,y2):
    return math.sqrt((x-x2)**2+(y-y2)**2)
for i in range(0,N):
    for j in range(0,N):
        M=M+dis(x[i],y[i],x[j],y[j])
print(M/N)
n = input()
l = list(input.split())

cnt = 0
max_height = 0
for i in range(len(l)):
  if l[i] > max_height:
    cnt +=1
    max_height = l[i]
    
print(cnt)   
  

### FIXED CODE ###

n = input()
l = list(input().split())
 
cnt = 0
max_height = 0
for i in range(len(l)):
  if int(l[i]) >= int(max_height):
    cnt +=1
    max_height = l[i]
    
print(cnt)
b = input()
if b=="A":
  print("T")
elif b=="T":
  print("A")
elif b=="G":
  print("C")
else
  print("G")

### FIXED CODE ###

b = input()
if b=="A":
  print("T")
elif b=="T":
  print("A")
elif b=="C":
  print("G")
elif b=="G":
  print("C")
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
import numpy as np

def main():
	n,m=map(int,input().split())
	s=input().rstrip().decode('utf-8')
	t=s[::-1]
	
	ans=[]
	
	now=0
	while now<n:
		for i in range(min(m,n-now),0,-1):
			
			if t[now+i]=="0":
				now+=i
				ans.append(i)
				break
			else:
				continue
		else:
			print(-1)
			exit(0)
	
	print(*ans[::-1])
	
	
	
	
	
	
	



if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

def main():
	n,m=map(int,input().split())
	s=input().rstrip().decode('utf-8')
	t=s[::-1]
	
	ans=[]
	
	now=0
	while now<n:
		for i in range(min(m,n-now),0,-1):
			
			if t[now+i]=="0":
				now+=i
				ans.append(i)
				break
			else:
				continue
		else:
			print(-1)
			exit(0)
	
	print(*ans[::-1])
	
	
	
	
	
	
	



if __name__ == "__main__":
	main()
n = int(input())
l = list(map(int,input().split()))
ans =[]
t = 0
for i , j in zip(l,l[1:]):
    if i < j:
        ans.append(t)
        t = 0
    else:
        t+=1
ans.append(t)
print(max(t))


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans =[]
t = 0
for i , j in zip(l,l[1:]):
    if i < j:
        ans.append(t)
        t = 0
    else:
        t+=1
ans.append(t)
print(max(ans))
N = int(input())
list_input = map(int, raw_input().split())

list_input = sorted(list_input)
sums = 0
for i in range(0,2*N,2):
    sums += min(list_input[i],list_input[i+1])

print(sums)


### FIXED CODE ###

N = int(raw_input())
L = map(int,raw_input().split())
L.sort(reverse = True)
ans = 0
for i in xrange(N):
    ans += min(L[2*i],L[2*i+1])
print ans
def prepare(N, MOD):
    fac = [None] * (N+2)
    finv = [None] * (N+2)
    inv = [None] * (N+2)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, N+1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
    return fac, finv

def combination(N, K, fac, finv, MOD):
    if N < K:
        return 0
    if N < 0 or K < 0:
        return 0
    else:
        return fac[N] * (finv[K] * finv[N - K] % MOD) % MOD

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

MOD = 10 ** 9 + 7
fac, finv = prepare(n, MOD)
ans = 2**n-1 - combination(n, a, fac, finv, MOD) - combination(n, b, fac, finv, MOD)
print(ans)

### FIXED CODE ###

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

MOD = 10 ** 9 + 7

def comb(n, r):
    ret = 1
    for i in range(r):
        ret *= n - i
        ret %= MOD
    for i in range(r):
        ret *= pow(i+1, MOD-2, MOD)
        ret %= MOD

    return ret % MOD
    

ans = pow(2, n, MOD) - 1 - comb(n, a) - comb(n, b)
ans %= MOD
print(ans)
N = int(input())
a = list(map(int,input().split()))
suma = a[0]
suma2 = sum(a)
for i in range(N-2):
    if 2*suma + a[i+1] -suma2 >= 0:
        break
    suma += a[i+1]
print(min(abs(2*suma+a[i] - suma2),abs(2*suma - suma2)))

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
suma = sum(a)
ans = abs(suma - a[0])
sumb = a[0]
if N == 2:
    print(abs(a[0]-a[1]))
else:
    for i in range(1,N-1):
        sumb += a[i]
        ans = min(ans,abs(suma - 2*sumb))
    print(ans)
n = int(input())
d = [[] for i in range(n)]
for i in range(n-1):
	a,b,x = map(int,input().split())
	a -= 1
	b -= 1
	x = x%2
	d[a].append([b,x])
	d[b].append([a,x])
color = [0]*n
used = set()
def dfs(v):
	for e,l in d[v]:
		if e not in used:
			used.add(e)
			if l == 1:
				color[e] = 1
			dfs(e)
dfs(0)
for c in color:
	print(c)

### FIXED CODE ###

n = int(input())
edges = [set() for _ in range(n)]
for i in range(n-1):
    u,v,w = [int(i)-1 for i in input().split()] 
    edges[u].add((v,w+1))
    edges[v].add((u,w+1))
ans = [-1]*n
q = [(0,0,-1)]
while q:
    v,d,p = q.pop()
    if d%2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u,w in edges[v]:
        if u == p:
            continue
        q.append((u,d+w,v))
for i in range(n):
    print(ans[i])
a,b=input()
if b%a==0:
    print(a+b)
else:
	print(b-a)

### FIXED CODE ###

n=list(map(int,input().split()))
if n[1]%n[0]==0:
    print(n[0]+n[1])
else:
    print(n[1]-n[0])
n, m = list(map(int, input().split()))
# a, b, c = list(map(int, input().split()))
a = [int(input()) for i in range(m)]

mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
j = 0
if 1 in a:
    point[1] = 0
    j += 1
else:
    point[1] = 1

for i in range(2, n+1):
    if i == a[j]:
        if j < m-1:
            j += 1
    else:
        point[i] = point[i-1]+point[i-2]
        point[i] %= mod

print(point[-1] % mod)


### FIXED CODE ###

n, m = list(map(int, input().split()))
# a, b, c = list(map(int, input().split()))
a = [int(input()) for i in range(m)]

mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
j = 0
if 1 in a:
    point[1] = 0
    if m >= 2:
        j += 1
else:
    point[1] = 1

if m == 0:
    a = [0]

for i in range(2, n+1):
    if i == a[j]:
        if j < m-1:
            j += 1
    else:
        point[i] = point[i-1]+point[i-2]
        point[i] %= mod

print(point[-1] % mod)
#!/bin/python3

import os
import sys


if __name__ == '__main__':
    a = input().split()
    b = input().split()
    c = input().split()

	result = c - (a - b)
    if result > 0:
      result = 0
    print(result)

### FIXED CODE ###

#!/bin/python3
 
import os
import sys


a = input().split()
result = int(a[2])+int(a[1])-int(a[0])
if result < 0:
  result = 0
print(result)
import numpy as np

def main():

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

  su = np.sum(A)
  av = su // N
  if su % N != 0:
    print(-1)
    return

  ans = N - 1
  b = 0
  c = 0

  for a in A[0: -1]:
    b += a
    c += 1
    if b == (c * av):
      ans -= 1
      b = 0
      c = 0

  print(ans)

main()

### FIXED CODE ###

import numpy as np

def main():

  W, A, B = map(int, input().split())
  
  A_ = A + W
  B_ = B + W
  
  if (A <= B and B <= A_) or (A <= B_ and B_ <= A_):
    print(0)
    return

  print(min(abs(A_ - B), abs(A - B_)))

main()
import sys
def t(A,p,r):
 x=A[r][1];i=p-1
 for j in range(p,r):
  if A[j][1]<=x:i+=1;A[i],A[j]=A[j],A[i]
 A[i+1],A[r]=A[r],A[i+1]
 return i+1
def k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]and A[i][2]>A[i+1][2]:return'Not s'
 return'S'
n=int(input())
A=[(e[0],int(e[2:]),i)for i,e in enumerate(sys.stdin)]
k(A,0,n-1)
print(s(A)+'table')
print("\n".join(f"{a} {b}"for a,b in A[:2]))


### FIXED CODE ###

import sys
def t(A,p,r):
 x=A[r][1];i=p-1
 for j in range(p,r):
  if A[j][1]<=x:i+=1;A[i],A[j]=A[j],A[i]
 A[i+1],A[r]=A[r],A[i+1]
 return i+1
def k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]and A[i][2]>A[i+1][2]:return'Not s'
 return'S'
def m():
 A=[(e[0],int(e[2:]),i)for i,e in enumerate(sys.stdin)]
 k(A,0,n-1)
 print(s(A)+'table')
 print('\n'.join(f'{a} {b}'for a,b,_ in A))
if'__main__'==__name__: n=int(input());m()
N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h = sorted(h)

m = []
for i in range(N-K+1):
    m.append(h[i+2] - h[i])
print(min(m))

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h = sorted(h)

m = []
for i in range(N-K+1):
    m.append(h[i+K-1] - h[i])
print(min(m))
import sys
input=sys.stdin.buffer.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
def primes(n):#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]]
A,B = map(int,input().split())
if A == 1 or B == 1:
    print(1)
else:
    Min = min(A,B)
    pr = primes(Min)
    c = 0
    for i in pr:
        if A%i == 0 and B%i == 0:
            c += 1
    print(c+1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
import fractions
A,B = map(int,input().split())
if A == 1 or B == 1:
    print(1)
else:
    def factorization(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストを返す
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])
        if temp!=1:
            arr.append([temp, 1])
        if arr==[]:
            arr.append([n, 1])
        return arr
    c = fractions.gcd(A,B)
    arr = factorization(c)
    print(len(arr)+1)
N= int(input())

N1=N%10

if N1=2,4,5,7,9:
	print(hon)
elif N1=0,1,6,8:
	print(pon)
else:
  	print(bon)


### FIXED CODE ###

N= int(input())
 
N1=N%10
 
if N1==2:
	print("hon")
elif N1==4:
	print("hon")
elif N1==5:
	print("hon")
elif N1==7:
	print("hon")
elif N1==9:
	print("hon")
elif N1==0:
	print("pon")
elif N1==1:
	print("pon")
elif N1==6:
	print("pon")
elif N1==8:
	print("pon")
else:
  	print("bon")
S = int(input())

A = [0,0,1]
for i in range(3,S):
  A += [A[i-1] + A[i-3]]
print(A[i]%(10 ** 9 + 7))

### FIXED CODE ###

S = int(input())
 
A = [0,0,1]
if S == 1 or S == 2:
  print(0)
elif S == 3:
  print(1)
else:
  for i in range(3,S):
    A += [A[i-1] + A[i-3]]
  print(A[i] % (10 ** 9 + 7))
H, W = map(int, input().split(" "))

result = True
masu = [["0" for i in range(H+2)] for j in range(W+2)]
for h in range(1, H+1):
    s = "0"+input()+"0"
    masu[h] = list(s)

# print(masu)    

for h in range(1, H+1):
    for w in range(1, W+1):
        # print(h, w, masu[h][w])
        if masu[h][w] == "#":
            if not ((masu[h][w] == masu[h+1][w]) or (masu[h][w] == masu[h][w+1]) or (masu[h][w] == masu[h-1][w]) or (masu[h][w] == masu[h][w-1])):
                result = False
                break

if result:
    print("Yes")
else:
    print("No")

### FIXED CODE ###


H, W = map(int, input().split(" "))

# result = True
masu = [['.' for i in range(W+2)] for j in range(H+2)]
for h in range(H):
    s = "."+input()+"."
    masu[h+1] = s

# print(masu)

for h in range(1,H+1):
    for w in range(1,W+1):
        if masu[h][w] == "#":
            if "#" == masu[h+1][w] or "#" == masu[h][w+1] or "#" == masu[h-1][w] or "#" == masu[h][w-1]:
                pass
            else:
                # result = False
                print("No")
                exit()

print("Yes")
n, m = map(int, input().split());
A = [];
B = [];

for i in range(m):
  a, b = input().split();
  a = int(a);
  A.append(a);
  B.append(b);

AC_count = 0;
WA_count = 0;
AC_list = [];

#AC_listの作成
for i in range(m):
  if B[i] == "AC":
    if A[i] not in AC_list: 
      AC_list.append(A[i]);

AC_count = len(AC_list);

#WA_countの作成
for j in range(m):
  if A[i] in AC_list:
    if B[i] == "WA":
      WA_count += 1;

 print(AC_count, WA_count);


### FIXED CODE ###

n,m = map(int,input().split())
#ac,wa列を作成（pi問題がACならac[i]がTRUE、AC,WAに問わずwa[i]はwaの数）
ac, wa=[False]*n,[0]*n
for i in range(m):
  p,s = input().split()
  p=int(p)
  if s=='AC':
    ac[p-1]=True
  elif (s=='WA') and (ac[p-1]==False):
    wa[p-1]+=1

penalty, clear=0,0
for i,tf in enumerate(ac): #iはインデックス、tfはac[i]
  if tf:
    penalty += wa[i] #piがACされているとき、ペナルティ値を増やす
    clear += 1
print(clear, penalty)
from operator import itemgetter
import math
N, H = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)] 

ab.sort(key=itemgetter(0))

amax = max([i[0] for i in ab]) 
num = 0
dmg = 0

for a, b in ab:
    if b > amax:
        num += 1
        dmg += b
        if dmg >= H:
            jdg = True
            break
if not jdg:
    num += math.ceil((H - dmg) / amax)
print(num)

### FIXED CODE ###

from operator import itemgetter
import math
N, H = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)] 

ab.sort(key=itemgetter(1), reverse=True)

amax = max([i[0] for i in ab]) 
num = 0
dmg = 0
jdg = False

for a, b in ab:
    if b > amax:
        num += 1
        dmg += b
        if dmg >= H:
            jdg = True
            break
if not jdg:
    num += math.ceil((H - dmg) / amax)
print(num)
N, Q = map(int, input().split())

w = [[] for _ in range(N+1)]
for _ in range(N-1):
    A, B = map(int, input().split())
    w[A].append(B)

cnt = [0]*(N+1)
for _ in range(Q):
    P, X = map(int, input().split())
    cnt[P] += X

cnt_sum = [0]*(N+1)

def f(i, n):
    cnt_sum[i] = n+cnt[i]
    for t in w[i]:
        f(t, cnt_sum[i])

f(1, 0)

print(" ".join([str(c) for c in cnt_sum[1:]]))

### FIXED CODE ###

N, Q = map(int, input().split())

w = [[] for _ in range(N+1)]
for _ in range(N-1):
    A, B = map(int, input().split())
    w[A].append(B)
    w[B].append(A)

cnt = [0]*(N+1)
for _ in range(Q):
    P, X = map(int, input().split())
    cnt[P] += X

flag = [False]*(N+1)

q = [1]
while q:
    n = q.pop()
    flag[n] = True
    for i in w[n]:
        if flag[i]:
            continue
        flag[i] = True
        cnt[i] += cnt[n]
        q.append(i)

print(" ".join([str(c) for c in cnt[1:]]))
n,k,x,y = list(map(int,input().split()))
print(n*x+(y-x)*max(n-k,0))

### FIXED CODE ###

n,k,x,y = (int(input()) for i in range(4))
print(n*x+(y-x)*max(n-k,0))
N = int(input())
inputs = [int(input()) for i in range(N)]

points = [int(s) for s in inputs]
points_sorted = sorted(points)

get_point = sum(points)
if get_point % 10 != 0:
    print(get_point)
else:
    cand1 = get_point - points_sorted[0]
    cand2 = get_point - points_sorted[1]
    if (cand1 > cand2) and (cand1 % 10 != 0):
        print(cand1)
    elif (cand2 % 10 != 0):
        print(cand2)
    else:
        print(0)

### FIXED CODE ###

N = int(input())
inputs = [int(input()) for i in range(N)]

points = [int(s) for s in inputs]
points_sorted = sorted(points)

get_point = sum(points_sorted)
non_10 = [x for x in points_sorted if (x % 10 != 0)]

if get_point % 10 != 0:
    print(get_point)
elif non_10 == []:
    print(0)
else:
    print(get_point - min(non_10))
X, t = map(int, input).split())
X -= t
if X < 0:
  X = 0
print(X)

### FIXED CODE ###

X, t = map(int, input().split())
X -= t
if X < 0:
  X = 0
print(X)
S=list(input())
k=int(input())

cnt,ans=0,0
for i in range(1,len(S)):
  if S[i-1]==S[i]:
    cnt+=1
  else:
    cnt+=1
    ans+=cnt//2
    cnt=0
ans+=cnt//2
if S[0]==S[-1] and S[-1]!=S[-2]:
  print(ans*k+k-1)
else:
  print(ans*k)

### FIXED CODE ###

S=list(input())
k=int(input())

cnt,ans=0,0
T=S+S
for i in range(1,len(T)):
  if T[i-1]==T[i]:
    cnt+=1
  else:
    ans+=(cnt+1)//2
    cnt=0
  if i==len(S)-1:
    ans+=(cnt+1)//2
    tmp=ans

if len(S)==1:
  print(k//2)
  exit()
if len(S)==2:
  if S[0]==S[1]:
    print(k)
  else:
    print(0)
  exit()
  
if len(set(T))==1:
  if len(S)%2==0:
    print(len(S)//2*k)
  else:
    out=(len(S)//2)*(k-(k//2))+(len(S)//2+1)*(k//2)
    print(out)
  exit()
      
print(tmp+(ans-tmp)*(k-1))
S=str(input())
T=str(input())
ls = []
cnt = 0
if T in S:
    print(0)
else:
    for i in range(len(S)-len(T)):
        for j in range(len(T)):
            if T[j] != S[j+i]:
                #print (T[j],S[j+i])
                cnt += 1
        ls.append(cnt)
        cnt = 0
#print(ls)
    print(min(ls))


### FIXED CODE ###

S=str(input())
T=str(input())
ls = []
cnt = 0
for i in range(len(S)-len(T)+1):
    cnt = 0
    for j in range(len(T)):
        #print(i,j)
        if T[j] != S[j+i]:
            #print(T[j],S[j+i])
            cnt += 1
    ls.append(cnt)
#print(ls)
print(min(ls))
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]

ab_hash = {}
count = 0
price_sum = 0
for x in ab:
    ab_hash[x[0]] = x[1]
ab_key_sorted = sorted(ab_hash.items(), key=lambda x: x[0])
while M > 0:
    if M > ab_key_sorted[count][1]:
        price_sum += ab_key_sorted[count][0] * ab_key_sorted[count][1]
    else:
        price_sum += M * ab_key_sorted[count][0]
    M = M - ab_key_sorted[count][1]
    count += 1

print(price_sum)


### FIXED CODE ###

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]

ab_hash = {}
count = 0
price_sum = 0
for x in range(len(ab)):
    ab_hash[x] = [ab[x][0], ab[x][1]]
ab_key_sorted = sorted(ab_hash.items(), key=lambda x: x[1][0])

for y in ab_key_sorted:
    if M > y[1][1]:
        price_sum += y[1][0] * y[1][1]
    else:
        price_sum += y[1][0] * M
    M -= y[1][1]
    if M <= 0:
        break

print(price_sum)