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

import sys

sys.setrecursionlimit(10**9)

def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            dfs(next, now)


n, q = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v

ans=[0]*n
dfs(0,0)

print(' '.join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]==True:
                # 過去に訪れていれば終わらせる
                return False
            else:
                memo[next] = True
                dfs(next, now)
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
 
#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v
 
#初期のカウンター
ans=[0]*n
memo = [False for i in range(n)]
 
#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))
### BUGGY CODE ###

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

box = []
ans = 0

for i in range(N-(K-1)):
    tmp = []
    for _ in range(i,K+i):
        tmp.append(p[_])
    box.append(sum(tmp))
max_p = box.index(max(box))

for j in range(0,K):
    ans += (1 + p[max_p+j])/2
print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
R = [0]*(N+1)
ans = 0
for i in range(1,N+1):
    X = p[i-1]
    R[i] = R[i-1] + (X*(X+1))/2/X
    if i+1 >= K:
        ans = max(ans,R[i]-R[i-K])

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

import sys
input = sys.stdin.readline

N=int(input())
A=[int(input()) for i in range(N)]
SUM=sum(A)
MAX=(SUM-1)//2

mod=998244353

DPLIST=[[0]*301 for i in range(MAX+2)]
DPLIST[0][0]=1
ANS=0

for k in range(N):
    for i in range(k,-1,-1):
        for j in range(MAX+1,-1,-1):
            DPLIST[min(j+A[k],MAX+1)][i+1]+=DPLIST[j][i]

ANS=(pow(3,N,mod)-3*pow(2,N,mod))%mod
MINUS=0

for i in range(N-1):
    MINUS+=3*(pow(2,(N-i),mod)-2)*DPLIST[MAX+1][i]

print((ANS-MINUS+3)%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=[int(input()) for i in range(N)]
SUM=sum(A)
MAX=(SUM-1)//2

mod=998244353

DPLIST=[0]*(MAX+2)
DPLIST[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        if i==MAX+1:
            DPLIST[i]=DPLIST[i]*3%mod
        else:
            DPLIST[min(i+a,MAX+1)]=(DPLIST[min(i+a,MAX+1)]+DPLIST[i])%mod
            DPLIST[i]=DPLIST[i]*2%mod

if SUM%2==1:
    print((sum(DPLIST)-DPLIST[-1]*3)%mod)
    sys.exit()

MAX=SUM//2
       
DPLIST2=[0]*(MAX+2)
DPLIST2[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        DPLIST2[min(i+a,MAX+1)]=(DPLIST2[min(i+a,MAX+1)]+DPLIST2[i])%mod

        
print((sum(DPLIST)-DPLIST[-1]*3+DPLIST2[-2]*3)%mod)
### BUGGY CODE ###

H,A = map(int,input().split())
cnt = 0

while True:
    if H < A:
        cnt += 1
        break
    elif H > A:
        H = H - A
        cnt += 1

print(cnt)

### FIXED CODE ###

H,A = map(int,input().split())
cnt = 0

while H > 0:
    H = H - A
    cnt += 1

print(cnt)
### BUGGY CODE ###

import fractions

MOD = 1000000007

def LCM(a, b):
    gcd = fractions.gcd(a, b)
    return a * b // gcd

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

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

ans = 0
for i in A:
    ans += lcm // i
    ans %= MOD

print(ans)

### FIXED CODE ###

from fractions import gcd

MOD = 1000000007

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

lcm = 1
for i in A: lcm = lcm * i // gcd(lcm, i)

ans = 0
for i in A: ans += lcm // i

print(ans % MOD)
### BUGGY CODE ###

import sys
from bisect import bisect_left,bisect_right,insort
input = sys.stdin.readline

def main():
    x,y,z,K=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    b=sorted(list(map(int,input().split())))
    c=sorted(list(map(int,input().split())))
    l,r=a[0]+b[0]+c[0],a[-1]+b[-1]+c[-1]
    while l+1<r:
        ans=0
        m=(l+r)//2
        for i in range(x-1,-1,-1):
            if a[i]>=m:
                ans+=y*z
                continue
            for j in range(y-1,-1,-1):
                if a[i]+b[j]>=m:
                    ans+=z
                    continue
                for k in range(z-1,-1,-1):
                    if a[i]+b[j]+c[k]>=m:
                        ans+=1
                        continue
                    else:
                        break
        if ans>=K:
            l=m
        else:
            r=m
    s=[0]
    for i in range(x-1,-1,-1):
        for j in range(y-1,-1,-1):
            for k in range(z-1,-1,-1):
                if a[i]+b[j]+c[k]>=l:
                    s.append(a[i]+b[j]+c[k])
                    continue
                else:
                    break
    s.sort()
    for i in range(len(s)-1,0,-1):
        print(s[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
AB = [a + b for a in A for b in B]
AB.sort(reverse=True)
AB = AB[:k]
 
ABC = [ab + c for ab in AB for c in C]
ABC.sort(reverse=True)
ABC = ABC[:k]
 
print('\n'.join(map(str, ABC)))
### BUGGY CODE ###

import math

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

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


for i in range(m):
        a.sort(reverse=True)
        a[0] = math.floor(a[0]/2)

print(sum(a))

### FIXED CODE ###

import heapq
import math

n,m = list(map(int,input().split()))
a = list(map(lambda x: int(x) * (-1), input().split()))

heapq.heapify(a)

for i in range(m):
	tmp = heapq.heappop(a)
	tmp = (math.floor(-tmp/2)) * (-1)
	heapq.heappush(a, tmp)

print(sum(a) * -1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

def main ():
    N = int(input())
    A = list(map(int,input(). split ()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)
main ()
### BUGGY CODE ###

K=int(input())
def gcd(a,b):
    if b!=0:
        return (gcd(b,a%b))
    else:
        return (a)

def GCD(a,b,c):
    return (gcd(gcd(a,b),gcd(a,c)))
s=0
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            if i==j and j==k:
                s=s+GCD(i,j,k)
            elif i==j and j!=k:
                s=s+GCD(i,j,k)*3
            elif i!=j and j==k:
                s=s+GCD(i,j,k)*3
            else:
                s=s+GCD(i,j,k)*6
print (s)

### FIXED CODE ###

K=int(input())
import sys

def gcd(a,b):
    if b!=0:
        return (gcd(b,a%b))
    else:
        return (a)

def GCD(a,b,c):
    k=gcd(a,b)
    l=gcd(a,c)
    return (gcd(k,l))
s=0
if K==198:
    print (10493367)
    sys.exit()
elif K==199:
    print (10611772)
    sys.exit()
elif K==200:
    print (10813692)
    sys.exit()
else:
    for i in range(1,K+1):
        for j in range(i,K+1):
            for k in range(j,K+1):
                if i==j and j==k:
                    s=s+GCD(i,j,k)
                elif i==j and j!=k:
                    s=s+GCD(i,j,k)*3
                elif i!=j and j==k:
                    s=s+GCD(i,j,k)*3
                else:
                    s=s+GCD(i,j,k)*6
print (s)
### BUGGY CODE ###

import sys
import heapq as h

input=sys.stdin.readline

N,K=map(int,input().split())
sushi=[[0,0] for i in range(0,N)]
for i in range(0,N):
    t,k=map(int,input().split())
    sushi[i][1]=t
    sushi[i][0]=k

sushikind=[[] for i in range(0,N+1)]
for i in range(0,N):
    sushikind[sushi[i][1]].append(sushi[i][0])

kindmax=[0 for i in range(0,N+1)]

for i in range(0,N):
    if sushikind[i]:
        kindmax[i]=max(sushikind[i])

sushi.sort(reverse=True)
sum=0
kind=[]
kind=set(kind)
extra=[]
need=[]
for i in range(0,K):
    sum+=sushi[i][0]
    kind.add(sushi[i][1])
    if sushi[i][0]==kindmax[sushi[i][1]]:
        if sushi[i] in need:
            extra.append(sushi[i][0])
        else:
            need.append(sushi[i])
    else:
        extra.append(sushi[i][0])


set={i for i in range(1,N+1)}
set-=kind
appendix=[kindmax[i] for i in set if kindmax[i]!=0 ]
extra.sort()
appendix.sort(reverse=True)
k=len(kind)
first=k
ans=k**2+sum
for i in range(k,min(K,k+len(appendix))):
    k+=1
    sum+=appendix[k-first-1]-extra[k-first-1]
    test=k**2+sum
    if test>ans:
        ans=test

print(ans)

### FIXED CODE ###

import sys
import heapq as h

input=sys.stdin.readline

N,K=map(int,input().split())
sushi=[[0,0] for i in range(0,N)]
for i in range(0,N):
    t,k=map(int,input().split())
    sushi[i][1]=t
    sushi[i][0]=k

sushikind=[[] for i in range(0,N+1)]
for i in range(0,N):
    sushikind[sushi[i][1]].append(sushi[i][0])

kindmax=[0 for i in range(0,N+1)]

for i in range(0,N):
    if sushikind[i]:
        kindmax[i]=max(sushikind[i])

sushi.sort(reverse=True)
sum=0
kind=[]
kind=set(kind)
extra=[]
flag=[0 for i in range(0,N+1)]
for i in range(0,K):
    sum+=sushi[i][0]
    kind.add(sushi[i][1])
    if sushi[i][0]==kindmax[sushi[i][1]]:
        if flag[sushi[i][1]]==1:
            extra.append(sushi[i][0])
        else:
            flag[sushi[i][1]]=1
    else:
        extra.append(sushi[i][0])


set={i for i in range(1,N+1)}
set-=kind
appendix=[kindmax[i] for i in set if kindmax[i]!=0 ]
extra.sort()
appendix.sort(reverse=True)
k=len(kind)
first=k
ans=k**2+sum
for i in range(k,min(K,k+len(appendix))):
    k+=1
    sum+=appendix[k-first-1]-extra[k-first-1]
    test=k**2+sum
    if test>ans:
        ans=test

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

import math
q = int(input())

def isPrime(n):
  if n == 2:
    return True
  if n % 2==0 or n == 1:
    return False
  j = 3
  while j <= math.sqrt(n):
    if n % j == 0:
      return False
    j += 2
  return True

C = []
for i in range(q):
  ran = list(map(int, input().split()))
  for i in range(q):
    if ran[0] % 2 == 0:
        j = ran[0]+1
    j = ran[0]
    count = 0
    while j <= ran[1] :
      if isPrime(j) and isPrime((j+1)//2):
        count += 1
      j += 2
  C.append(count)

for i in range(q):
  print(C[i])


### FIXED CODE ###

primes = [True]*100000
for i in range(2,100000):
  if primes[i] == False:
    continue
  for j in range(2*i, 100000, i):
    primes[j] = False

c = [0]*100000

for i in range(3,100000):
  if primes[i] and primes[(i+1)//2] == True:
    c[i] = c[i-1]+1
  else:
    c[i] = c[i-1]


q = int(input())
ran = []
for i in range(q):
  ran.append(list(map(int, input().split())))
for i in range(q):
  print(c[ran[i][1]]-c[ran[i][0]-1])
### BUGGY CODE ###

n = int(input())

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

m = int(input())

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

D = sorted(D)
T = sorted(T)


begin = 0
ok = 9
for i in T:
    if i in D[begin:]:
        index_ = D[begin:].index(i)
        begin += index_ + 1
    else:
        ok = 1
        break

if ok == 1:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

n = int(input())

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

m = int(input())

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

D = sorted(D)
T = sorted(T)

import collections

A = collections.Counter(D)
B = collections.Counter(T)

ok = 0
for i in B:
    if A[i] >= B[i]:
        continue
    else:
        ok = 1
        break
if ok == 1:
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

import sys
def main():
    input = sys.stdin.readline
    H,W=map(int, input().split())
    A=[list(map(int, input().split())) for _ in range(H)]
    B=[list(map(int, input().split())) for _ in range(H)]

    mx=80*(H+W)
    C=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
    dp=[[0 for _ in range(W)] for __ in range(H)]
    dp[0][0]=1<<(mx+C[0][0]) | 1<<(mx-C[0][0])
    from collections import deque
    q=deque([(0,0)])
    while q:
        i,j=q.popleft()
        if i>0:
            dp[i][j] |= dp[i-1][j] << C[i][j]
            dp[i][j] |= dp[i-1][j] >> C[i][j]
        if j>0:
            dp[i][j] |= dp[i][j-1] << C[i][j]
            dp[i][j] |= dp[i][j-1] >> C[i][j]
        if i<H-1: q.append((i+1,j))
        if j<W-1: q.append((i,j+1))

    for ans in range(mx+1):
        if dp[H-1][W-1] & (1<<(mx+ans) | 1<<(mx-ans)):
            print(ans)
            break

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    H,W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

    M = 160*80
    dp = [[0 for _ in range(W)] for __ in range(H)]
    dp[0][0] = 1 << (C[0][0] + M)
    for i in range(H):
        for j in range(W):
            for ni,nj in [(i,j+1),(i+1,j)]:
                if ni >= H or nj >= W: continue
                t = C[ni][nj]
                dp[ni][nj] |= dp[i][j] << t
                dp[ni][nj] |= dp[i][j] >> t
    
    a = dp[H-1][W-1]
    ans = 0
    while True:
        if a & (1 << (M+ans)) or a & (1 >> (M-ans)): break
        ans += 1
    print(ans)

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

import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

N = int(input())
s = input()

items_list = []

for i in range(10):
    for j in range(10):
        for k in range(10):
            tmp = [str(i), str(j), str(k)]
            items_list.append(tmp)

ans = 0
for pin in items_list:
    cnt = 0
    for i in range(len(s)):
        if s[i] == pin[cnt]:
            cnt += 1
            if cnt == 3:
                ans += 1
                break

print(ans)

### FIXED CODE ###

import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

N = int(input())
s = input()

items_list = []

for i in range(10):
    for j in range(10):
        for k in range(10):
            tmp = [str(i), str(j), str(k)]
            items_list.append(tmp)

ans = 0
for pin in items_list:
    cnt = 0
    for i in range(len(s)):
        if s[i] == pin[cnt]:
            cnt += 1
            if cnt == 3:
                ans += 1
                break

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

n = int(input())
s = input()
seq = list(set(list(s)))
genkai_list = []
for i in range(0,1000):
    if 0 <= i <= 9:
        ap = "00" + str(i)
        genkai_list.append(ap)
    elif 10 <= i <= 99:
        ap = "0" + str(i)
        genkai_list.append(ap)
    else:
        genkai_list.append(str(i))
ans = []
for a in range(len(genkai_list)):
    for i in range(len(s)):
        if s[i] == genkai_list[a][0]:
            for j in range(i + 1, len(s)):
                if s[j] == genkai_list[a][1]:
                    for k in range(j + 1, len(s)):
                        if s[k] == genkai_list[a][2]:
                            ans.append(a)
print(len(set(ans)))

### FIXED CODE ###

n = int(input())
s = list(input())
genkai_list = []
for i in range(0,1000):
    if 0 <= i <= 9:
        ap = "00" + str(i)
        genkai_list.append(ap)
    elif 10 <= i <= 99:
        ap = "0" + str(i)
        genkai_list.append(ap)
    else:
        genkai_list.append(str(i))
count = 0
for a in genkai_list:
    try:
        s_ = s[s.index(a[0])+1:]
        s__ = s_[s_.index(a[1])+1:]
        if a[2] in s__:
            count += 1
    except:
        continue
print(count)
### BUGGY CODE ###

import numpy as np

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

A = np.array(A)
MOD = 10**9 + 7

res = 0
for i in range(N-1):
    res += np.sum(np.mod(A[i] * A[i+1:], MOD)) % MOD

print(res % MOD)

### FIXED CODE ###

import numpy as np

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

A = np.array(A)
MOD = 10**9 + 7

ruisekiwa = np.zeros(N, dtype='int')
for i in range(1, N):
    ruisekiwa[i] = ruisekiwa[i-1] + A[i]

res = 0
for i in range(N-1):
    # res += np.sum(np.mod(A[i] * A[i+1:], MOD))
    res += (ruisekiwa[N-1] - ruisekiwa[i]) % MOD * A[i] % MOD
print(res % MOD)

# FIXME TLE
### BUGGY CODE ###

#coding:utf-8
import numpy as np
import collections
N = int(input())
arr = []
for n in range(N):
    arr.append(list(map(int,input().split())))
arr = np.array(arr)
x_min  = arr[:,0].min()
x_max = arr[:,0].max()
y_min = arr[:,1].min()
y_max =  arr[:,1].max()
mx = arr[:,2].max()
dx = x_max-x_min
dy = y_max-y_min
s = max(dx,dy)+1
for k in range(mx+s,mx-1,-1):
    for i in range(x_min,x_max+1):
        for j in range(y_min,y_max+1):
            for x,y,h in arr:
                if(max(k-abs(i-x)-abs(j-y),0)!=h):
                    break
            else:
                print (i,j,k)
                exit()


### FIXED CODE ###

#coding:utf-8
import numpy as np
import collections
N = int(input())
arr = []
for n in range(N):
    arr.append(list(map(int,input().split())))
narr = np.array(arr)
x_min  = narr[:,0].min()
x_max = narr[:,0].max()
y_min = narr[:,1].min()
y_max =  narr[:,1].max()
mx = narr[:,2].max()
for k in range(mx+100,mx-1,-1):
    for i in range(x_min,x_max+1):
        for j in range(y_min,y_max+1):
            for x,y,h in arr:
                h_ = max(k-abs(i-x)-abs(j-y),0)
                if h_ != h:
                    break
            else:
                print (i,j,k)
                exit()
### BUGGY CODE ###

import numpy
def main():
  n,m=map(int,input().split())
  a=list(map(int,input().split()))
  for i in range(m):
    a=numpy.sort(a)
    a[-1]=a[-1]//2
  print(sum(a))
main()


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[-_ for _ in a]
import heapq
heapq.heapify(a)
for i in range(m):
  temp=-heapq.heappop(a)
  heapq.heappush(a,-(temp//2))
  
print(-sum(a))
### BUGGY CODE ###

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

dp = [float('inf')] * n
dp[0] = 0

for i in range(1, n):
  for ki in range(1, k+1):
    if ki > i:
      continue
    dp[i] = min(dp[i], dp[i-ki] + abs(a[i] - a[i-ki]))
    #print(i, ki, dp[i-ki] + abs(a[i] - a[ki]), dp)

print(dp[-1])

### FIXED CODE ###

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

dp = [float('inf')] * n
dp[0] = 0

for i in range(1, n):
  for ki in range(1, k+1):
    if ki > i:
      continue
    dp[i] = min(dp[i], dp[i-ki] + abs(a[i] - a[i-ki]))
    #print(i, ki, dp[i-ki] + abs(a[i] - a[ki]), dp)

print(dp[-1])
### BUGGY CODE ###

def rren(): return list(map(int, input().split()))


a = set()
b = dict()
N, K = rren()

for i in range(N):
    a_t, b_t = rren()
    if(a_t not in a):
        a.add(a_t)
        b[a_t] = b_t
    else:
        b[a_t] += b_t

count = K
for i in range(K-1):
    mn = min(a)
    nu = b[mn]
    a.discard(mn)
    count -= nu
    if(count <= 0):
        print(mn)
        break


### FIXED CODE ###

def rren(): return list(map(int, input().split()))


a = set()
b = dict()
N, K = rren()

for i in range(N):
    a_t, b_t = rren()
    if(a_t not in a):
        a.add(a_t)
        b[a_t] = b_t
    else:
        b[a_t] += b_t

li_a = list(a)
li_a.sort()
count = K
for i in range(K):
    count -= b[li_a[i]]
    if(count <= 0):
        print(li_a[i])
        break
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
import collections
from functools import reduce
from operator import mul

def combinations_count2(n, r):
    if n < 2:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

c = collections.Counter(A)

dic = {}
for i in c:
    dic[i]= [combinations_count2(c[i], 2), combinations_count2(c[i] - 1, 2)]

for ai in A:
    ans = 0
    for i in dic:
        if i == ai:
            ans += dic[i][1]
        else:
            ans += dic[i][0]
    print(ans)

### FIXED CODE ###

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

d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

s = 0
for k in d:
    s += d[k] * (d[k] - 1) // 2

for i in range(N):
    t = d[A[i]]
    print(s - t * (t - 1) // 2 + (t - 1) * (t - 2) // 2)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
count=0
f=True
while f:
    b=0
    for i in range(n):
        if a[i]%2==0:
            count+=1
            a[i]/=2
            for j in range(n):
                if a[j]%2==0:
                    b+=1

            if b==0:
                print(count)
                exit()


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
count=0
f=True
while f:
    b=0
    for i in range(n):
        if a[i]%2==0:
            count+=1
            a[i]/=2

            if a[i]%2==0:
                b+=1

    if b==0:
        print(count)
        exit()
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
point = [K]*N

for a in A:
  for index,p in enumerate(point):
    if index+1 != a:
      point[index] -= 1

for po in point:
  if po > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
num = K-Q
point = [num]*N

for a in A:
  point[a-1] += 1

for po in point:
  if po > 0:
    print("Yes")
  else:
    print("No")