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

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
vi,wi=[],[]
for i in range(N):
    w,v=map(int,input().split())
    wi.append(w)
    vi.append(v)

M=int(sum(vi))
dp1=[sum(wi)+1]*(M+1)
#dp2=[sum(wi)+1]*(M+1)
dp1[0]=0
   
#L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in zip(wi,vi):
    s+=v
    for j in range(min(s,M),-1,-1):
        if j >= v: 
            if dp1[j] > dp1[j-v]+w: dp1[j]=dp1[j-v]+w
        if dp1[j] > dp1[j]: dp1[j]=dp1[j]
    #print(dp1)
    #print(dp2)
    #dp1=[dp2[i] for i in range(M+1)]    
    
#print(max(dp))
m=0
for i in range(M+1):
    if dp1[i]<=W:
        m=i
print(m)
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
vi,wi=[],[]
for i in range(N):
    w,v=map(int,input().split())
    wi.append(w)
    vi.append(v)
    

#L = sorted([list(map(int,input().split())) for i in range(N)])

M=int(sum(vi))
dp=[W+1]*(M+1)
dp[0]=0
   
#L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in zip(wi,vi):
    s+=v
    for j in range(min(s,M),v-1,-1):
        if dp[j] > dp[j-v]+w: dp[j]=dp[j-v]+w
    #print(dp)

m=0
for i in range(M+1):
    if dp[i]<=W:
        m=i
print(m)
### BUGGY CODE ###

H, W = map(int, input().split())
A = [None]*H
for i in range(H):
    A[i] = list(map(int, input().split()))
B = [None]*H
for i in range(H):
    B[i] = list(map(int, input().split()))

# C: A-Bの絶対値を持つ
C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

INF = 10**12
K = 2*80*(H+W-1)
dp = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]# 答えから80*(H+W-1)を引く
dp[0][0][80*(H+W-1)+C[0][0]] = 1
dp[0][0][80*(H+W-1)-C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(K+1):
            if i > 0 and dp[i-1][j][k] > 0:
                dp[i][j][k+C[i][j]] += dp[i-1][j][k]
                dp[i][j][k-C[i][j]] += dp[i-1][j][k]
            if j > 0 and dp[i][j-1][k] > 0:
                dp[i][j][k+C[i][j]] += dp[i][j-1][k]
                dp[i][j][k-C[i][j]] += dp[i][j-1][k]
ans = INF
for k in range(K+1):
    res = dp[H-1][W-1][k]
    if res > 0:
        ans = min(ans, abs(k-80*(H+W-1)))
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
A = [None]*H
for i in range(H):
    A[i] = list(map(int, input().split()))
B = [None]*H
for i in range(H):
    B[i] = list(map(int, input().split()))

# C: A-Bの絶対値を持つ
C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

K = 80*(H+W-1)//2 + 1# 80*(H+W-1)の半分を超えるのは無駄
dp = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]# 答えから80*(H+W-1)を引く
dp[0][0][C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(K+1):
            if i and dp[i-1][j][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1
            if j and dp[i][j-1][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1

for k in range(K+1):
    res = dp[H-1][W-1][k]
    if res:
        print(k)
        break
### BUGGY CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output


def chkprint(*args):
    names = {id(v): k for k, v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg), '???')+' = '+repr(arg) for arg in args))

# Binary converter


def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]

# --------------------------------------------


dp = None


def main():
    N = int(input())
    X = li_input()

    sX = sorted(X)

    for x in X:
        idx = sX.index(x)
        sX.pop(idx)
        print(sX[len(sX) // 2])
        sX.insert(idx, x)


main()


### FIXED CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output


def chkprint(*args):
    names = {id(v): k for k, v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg), '???')+' = '+repr(arg) for arg in args))

# Binary converter


def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]

# --------------------------------------------


dp = None


def main():
    N = int(input())
    X = li_input()

    sX = sorted(X)
    med = sX[len(sX) // 2]
    med_min = sX[len(sX) // 2 - 1]

    for x in X:
        if x < med:
            print(med)
        else:
            print(med_min)


main()
### BUGGY CODE ###

def main():
    n = int(input())
    m = map(int, input().split())
    ans = 1
    for i in m:
        ans *= i
    print(ans) if ans <= 1000000000000000000 else print(-1) 
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    m = list(map(int, input().split()))
    ans = 1
    if min(m) == 0:
        print(0)
    else:
        m.sort(reverse=True)
        for i in m:
            ans *= i
            if ans > 1000000000000000000:
                ans = -1
                break
        print(ans) 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
loop_flags = [False] * N
loops = []
for i in range(N):
    if loop_flags[i]:
        continue
    next_cell = i
    loop = []
    while not loop_flags[next_cell]:
        loop_flags[next_cell] = True
        loop.append(C[next_cell])
        next_cell = P[next_cell] - 1
    if loop:
        loops.append(loop)
# print(loops)
ans = C[0]
for loop in loops:
    work_loop_sum = []
    now = 0
    tmp_ans = 0
    one_loop_point = sum(loop)
    if one_loop_point <= 0 or K <= len(loop):
        for i in range(1, K + 1):
            tmp_ans = sum(loop[:i])
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]
    else:
        for i in range(K + 1):
            tmp_ans = sum(loop[:i]) + ((K - i) // len(loop)) * one_loop_point
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
loop_flags = [False] * N
loops = []
for i in range(N):
    if loop_flags[i]:
        continue
    next_cell = i
    loop = []
    while not loop_flags[next_cell]:
        loop_flags[next_cell] = True
        loop.append(C[next_cell])
        next_cell = P[next_cell] - 1
    if loop:
        loops.append(loop)
# print(loops)
ans = C[0]
for loop in loops:
    work_loop_sum = []
    now = 0
    tmp_ans = 0
    one_loop_point = sum(loop)
    if one_loop_point <= 0 or K <= len(loop):
        for i in range(1, min(K + 1, len(loop) + 1)):
            tmp_ans = sum(loop[:i])
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]
    else:
        for i in range(min(K + 1, len(loop) + 1)):
            tmp_ans = sum(loop[:i]) + ((K - i) // len(loop)) * one_loop_point
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]

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

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
for i in range(1, n + 1):
    print("YNeos"[k - q + a.count(i) < 1::2])

### FIXED CODE ###

n, k, q = map(int, input().split())
d = dict()
for i in range(n):
    d[i + 1] = 0
for i in range(q):
    d[int(input())] += 1
for i in range(n):
    print("YNeos"[(q - k) >= d[i + 1]::2])
### BUGGY CODE ###

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m,k=map(int,input().split())
s=set()
uf=UnionFind(n+1)
r=set()
for i in range(m):
  a,b=map(int,input().split())
  s.add((a,b))
  s.add((b,a))
  uf.unite(a,b)
for j in range(k):
  c,d=map(int,input().split())
  s.add((c,d))
  s.add((d,c))
for i in range(1,n+1):
  r.add(uf.find(i))
ans=[0]*(n+1)
for i in r:
  arr=uf.members(i)
  v=uf.size(i)
  for j in arr:
    for k in arr:
      if j==k:continue
      if (j,k) in s:
        ans[j]-=1
        ans[k]-=1
  for j in arr:
    ans[j]=v-1+ans[j]//2
print(*ans[1:])

### FIXED CODE ###

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m,k=map(int,input().split())
uf=UnionFind(n+1)
cnt=[0]*(n+1)
for i in range(m):
  a,b=map(int,input().split())
  uf.unite(a,b)
  cnt[a]+=1
  cnt[b]+=1
for i in range(k):
  c,d=map(int,input().split())
  if uf.same(c,d):
    cnt[c]+=1
    cnt[d]+=1
ans=[]
for i in range(1,n+1):
  ans.append(uf.size(i)-cnt[i]-1)
print(*ans)
### BUGGY CODE ###

def search(string,n):
    l=[]
    for i in range(1000):
        s=str(i)
        if len(s)==1:
            s='00'+s
        elif len(s)==2:
            s='0'+s
        l.append(s)
    cnt=0
    for i in range(1000):
        k=0
        for j in range(n):
            if k==2 and l[i][k]==string[j]:
                cnt+=1
                #print(l[i])
                break
            if l[i][k]==string[j]:
               k+=1
    
    return cnt
    
    

n=int(input())
s=input()
l=search(s,n)
print(l)


### FIXED CODE ###

def search(string,n):
    cnt=0
    for i in range(1000):
        s=str(i)
        if len(s)==1:
            s='00'+s
        elif len(s)==2:
            s='0'+s
        k=0
        for j in range(n):
            if k==2 and s[k]==string[j]:
                cnt+=1
                #print(l[i])
                break
            if s[k]==string[j]:
               k+=1
    
    return cnt
    
    

n=int(input())
s=input()
l=search(s,n)
print(l)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
from pprint import pprint
h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch-=1;cw-=1
dh,dw=map(int,input().split())
dh-=1;dw-=1
s=[input() for _ in range(h)]

from collections import deque
visited=[[0]*w for _ in range(h)]
q=deque()
p=deque()
q.append((ch,cw))
cur=0
while q:
    while q:
        # print("q",q)
        # print("p",p)
        x,y=q.popleft()
        visited[x][y]=1

        for i,j in [(-1,0),(1,0),(0,1),(0,-1)]:
            xx=x+i
            yy=y+j
            if xx<0 or h<=xx:
                continue
            if yy<0 or w<=yy:
                continue
            
            if visited[xx][yy]==0 and s[xx][yy]==".":
                visited[xx][yy]=1
                q.append((xx,yy))

        for i in range(-2,3):
            for j in range(-2,3):
                if abs(i)+abs(j)<=1:
                    continue
                xx=x+i
                yy=y+j
                if xx<0 or h<=xx:
                    continue
                if yy<0 or w<=yy:
                    continue
                
                if visited[xx][yy]==0 and s[xx][yy]==".":
                    p.append((xx,yy))

    # print(q,p,visited)
    if visited[dh][dw]:
        print(cur)
        exit()
    
    cur+=1
    q=p
    p=deque()
print(-1)
  
    

### FIXED CODE ###

from pprint import pprint
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch-=1;cw-=1
dh,dw=map(int,input().split())
dh-=1;dw-=1
INF=float("inf")
maze=[input() for _ in range(h)]
dist=[[INF]*w for _ in range(h)]
q=deque()
p=[]
q.append((ch,cw))
dist[ch][cw]=0
cur=0
# pprint(dist)
# exit()
while q:
    while q:
        x,y=q.popleft()
        # (x,y)は到達訪問済み
        d=dist[x][y]
        for i in range(-2,3):
            for j in range(-2,3):
                # absの和が1、上下左右
                if abs(i)+abs(j)==1:
                    xx=x+i
                    yy=y+j
                    # 範囲内の時
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        # 道のとき
                        if maze[xx][yy]==".":
                            # 未到達の時
                            if dist[xx][yy]>d:
                                # 移動前のdist[x][y]と同じコスト
                                dist[xx][yy]=d
                                q.append((xx,yy))
                # ワープ 
                if abs(i)+abs(j)>=2:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if maze[xx][yy]==".":
                            if dist[xx][yy]>d+1:
                                dist[xx][yy]=d+1
                                p.append((xx,yy))
                                
   
    cur+=1
    q=deque(p)
    p=[]
            

# pprint(dist)
ans=dist[dh][dw]
if ans==INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

def m():
    n, M, Q = map(int, input().split())
    a = [[0 for _ in range(n+1)] for _ in range(n+1)]
    for i in range(M):
        l, r = map(int, input().split())
        a[l][r] += 1

    for i in range(Q):
        p, q = map(int, input().split())
        ans = 0
        for j in range(p, q+1):
            for k in range(p, q + 1):
                ans += a[j][k]
        print(ans)

m()

### FIXED CODE ###

def m():
    n, M, Q = map(int, input().split())
    a = [[0 for _ in range(n+1)] for _ in range(n+1)]
    b = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(M):
        l, r = map(int, input().split())
        a[l][r] += 1

    for i in range(1, n+1):
        b[1][i] += a[1][i] + b[1][i-1]
    for i in range(2, n+1):
        b[i][1] += a[i][1] + b[i-1][1]

    for i in range(1, n+1):
        for j in range(1, n+1):
            b[i][j] = a[i][j] + b[i-1][j] + b[i][j-1] - b[i-1][j-1]

    for i in range(Q):
        p, q = map(int, input().split())
        ans = b[q][q] + b[p-1][p-1] - b[q][p-1] - b[p-1][q]
        print(ans)

m()
### BUGGY CODE ###

import copy
N,K,C= map(int,input().split())
S = input()
T = [n for n, v in enumerate(S) if v == "o"]

a,b=[T[0]],[T[-1]]

for i in range(len(T)):
  if len(a)!=K:
    if T[i]-a[-1]>C:
      a.append(T[i])
  if len(b)!=K:
    if b[0]-T[-i-1]>C:
      b.insert(0,T[-i-1])
      
for i in range(K):
  if a[i]==b[i]:
    print(a[i]+1)
  

### FIXED CODE ###

N,K,C= map(int,input().split())
S = input()
T = [n for n, v in enumerate(S) if v == "o"]

a,b=[T[0]],[T[-1]]

for i in range(len(T)):
  if len(a)!=K:
    if T[i]-a[-1]>C:
      a.append(T[i])
  if len(b)!=K:
    if b[-1]-T[-i-1]>C:
      b.append(T[-i-1])
      
for i in range(K):
  if a[i]==b[-i-1]:
    print(a[i]+1)
### BUGGY CODE ###

n,k = map(int,input().split()) 
a = list(map(int,input().split()))
i = 0
max_exp = 0
while i + k <= n:
    exp = 0
    for j in range(k):
        exp += a[i+j]
    if max_exp < exp:
        max_exp = exp
        i += 1
    else:
        i += 1
print((k+max_exp)/2)

### FIXED CODE ###

n,k = map(int,input().split()) 
a = list(map(int,input().split()))
max_a = [sum(a[0:k])]
exp = max_a[0]
for i in range(n-k):
    max_a.append(max_a[i]-a[i]+a[k+i])
    if max_a[i+1] > exp:
      exp = max_a[i+1]
print((k+exp)/2)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = str(input())
li = []

for i in range(N-1):
  if S[i]=='A' and S[i+1]=='C':
    li.append(1)
  else:
    li.append(0)

for i in range(Q):
  l, r = map(int, input().split())
  ans = sum(li[:r-1]) - sum(li[:l-1])
  print(ans)


### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
li = []
cnt = 0

for i in range(N-1):
  if S[i]=='A' and S[i+1]=='C':
    cnt += 1
    li.append(cnt)
  else:
    li.append(cnt)

for i in range(Q):
  l, r = map(int, input().split())
  if l > 1:
    ans = li[r-2] - li[l-2]
  else:
    ans = li[r-2]
  print(ans)
### BUGGY CODE ###

N = int(input())
from math import gcd
prime = [0] * 2 + [1] * (10 ** 6 - 1)
A = list(map(int, input().split()))
A.sort()
g = 0
for a in A:
  g = gcd(g, a)
for i in range(2, 10 ** 2 + 1):
  if prime[i]:
    for j in range(2 * i, 10 ** 3 + 1, i):
      prime[j] = 0
P = [i for i in range(2, 10 ** 3 + 1) if prime[i]]
from bisect import bisect
A = A[bisect(A, 1):]
N = len(A)
x = [0] * (10 ** 6 + 1)
for a in A:
  for p in P:
    if a % p == 0:
      x[p] += 1
      while a % p == 0:
        a //= p
    if a == 1:
      break
  if a > 1:
    x[a] += 1
if max(x) < 2:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
  
else:
  print('not coprime')

### FIXED CODE ###

N = int(input())
from math import gcd
prime = [0] * 2 + [1] * (10 ** 6 - 1)
A = list(map(int, input().split()))
A.sort()
g = 0
for a in A:
  g = gcd(g, a)
for i in range(2, 10 ** 2 + 1):
  if prime[i]:
    for j in range(2 * i, 10 ** 3 + 1, i):
      prime[j] = 0
P = [i for i in range(2, 10 ** 3 + 1) if prime[i]]
from bisect import bisect
A = A[bisect(A, 1):]
N = len(A)
x = [0] * (10 ** 6 + 1)
if N <= 80000:
  for a in A:
    for p in P:
      if a % p == 0:
        x[p] += 1
        while a % p == 0:
          a //= p
      if a == 1:
        break
    if a > 1:
      x[a] += 1
  if max(x) < 2:
    print('pairwise coprime')
    exit()
if g == 1:
  print('setwise coprime')
  
else:
  print('not coprime')
### BUGGY CODE ###

N = int(input())
a_lis = [int(input()) for _ in range(N)]

now = 1
flag = 1
memo = []
cnt = 0
for i in range(N):
    next = a_lis[now-1]
    if next in memo:
        print(-1)
        flag = 0
        break
    else:
        memo.append(next)
        now = next
    cnt+=1
    if next ==2:
        print(cnt)
        break


### FIXED CODE ###

N = int(input())
a_lis = [int(input()) for _ in range(N)]

now = 1
flag = 1
cnt = 0
while cnt<N and next!=2:
    cnt+=1
    next = a_lis[now-1]
    now = next
if next==2:print(cnt)
else:print(-1)
### BUGGY CODE ###

n,k = map(int,input().split())
hlist = [int(input())for i in range(n)]
hlist.sort()
dlist = [0]*(n-1)

ans = float('inf')
i = 0
while i+(k-1) <= n-1:
  ans = min(ans, sum((hlist[j+1]-hlist[j]for j in range(i,k-1+i))))
  i += 1

print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
hlist = sorted([int(input())for i in range(n)])

ans = 10**9
i = 0

while i+(k-1) <= n-1:
  ans = min(ans, hlist[k+i-1]-hlist[i])
  i += 1

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

import numpy

tmp=input()
list=input().split(" ")
array=numpy.zeros(len(list),dtype=">i4")
for i in range(len(list)):
  array[i]=int(list[i])

a=int(input())#-1

for i in range(a):
  b=input().split(" ")
  if int(b[0]) in array:
    array=numpy.where(array==int(b[0]),int(b[1]),array)
#    for j in pos:
#      array[j]=int(b[1])
    sum=numpy.sum(array)
    print(sum)
  else:
    sum=numpy.sum(array)
    print(sum)
  

### FIXED CODE ###

import numpy

tmp=input()
list=input().split(" ")
list=[int(x) for x in list]
array=numpy.array(list,dtype=">i4")
sum=numpy.sum(array)
all=numpy.zeros(100001,dtype=">i4")
for i in array:
  all[i]+=1
#for i in range(len(list)):
#  array[i]=int(list[i])

a=int(input())

for i in range(a):
  b=input().split(" ")
  b0=int(b[0])
  b1=int(b[1])
  diff=all[b0]*(b1-b0)
  sum+=diff
  all[b1]+=all[b0]
  all[b0]=0
  print(sum)
### BUGGY CODE ###

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

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
m=a[0]
ans=0
for i in range(n):
    x=a[i]
    if x<=m:
        ans+=1
        m=x
print(ans)
### BUGGY CODE ###

from heapq import *
def abc144c():
  n,k=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  f=sorted(list(map(int,input().split())))[::-1]
  q=[]
 
  for i,j in zip(a,f):
    heappush(q,(-i*j,j))
  for i in range(k):
    tmp,key=heappop(q)
    heappush(q,(tmp+key,key))
  ans,key=heappop(q)
  print(-ans)
abc144c()

### FIXED CODE ###

n,k=map(int,input().split())
abilities=sorted(list(map(int,input().split())))
foods=sorted(list(map(int,input().split())),reverse=True)

if sum(abilities)<=k:
  print(0)
  exit()
  
def check(score):
  ret=0
  for a,f in zip(abilities,foods):
    ret+=max(0,(a*f-score+f-1)//f)
  return ret<=k

ok=10**12+1
ng=0
for _ in range(50):
  mid=(ok+ng)//2
  if check(mid):
    ok=mid
  else:
    ng=mid
print(ok)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def update(node,value):
  if node-1<0 or len(l)<=node-1:
    return 0
  vl[node-1]+=value
  if len(l[node-1])==0:
    return 0
  for x in l[node-1]:
    update(x,value)

n,q=LI()

l=[[] for _ in range(n)]
vl=[0 for _ in range(n)]

for _ in range(n-1):
  a,b=LI()
  l[a-1].append(b)

for _ in range(q):
  a,b=LI()
  update(a,b)

# print(l)
# print(vl)
print(' '.join([str(x) for x in vl]))



### FIXED CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

nmax=2*10**5+10
graph=[[] for _ in range(nmax)]
level=[-1]*nmax

def dfs(n,s,l):
  if len(graph[s])==0:
    return
  for e in graph[s]:
    if level[e]==-1:
      level[e]=level[s]+1
    if level[e]>level[s]:
      l[e]+=l[s]
      dfs(n,e,l)

def main():
  n,q=LI()
  for _ in range(n-1):
    a,b=LI()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
  l=[0]*n
  for _ in range(q):
    a,b=LI()
    l[a-1]+=b

  level[0]=0
  dfs(n,0,l)

  return ' '.join([str(x) for x in l])

# main()
print(main())