Problem:


Score : 300 points

Problem Statement

There is an empty array.
The following N operations will be performed to insert integers into the array.
In the i-th operation (1≤i≤N), b_i copies of an integer a_i are inserted into the array.
Find the K-th smallest integer in the array after the N operations.
For example, the 4-th smallest integer in the array \{1,2,2,3,3,3\} is 3.

Constraints

1≤N≤10^5 

1≤a_i,b_i≤10^5 

1≤K≤b_1…+…b_n

All input values are integers.

Input

Input is given from Standard Input in the following format:  

N K
a_1 b_1
:  
a_N b_N

Output

Print the K-th smallest integer in the array after the N operations.  

Sample Input 1

3 4
1 1
2 2
3 3

Sample Output 1

3

The resulting array is the same as the one in the problem statement.

Sample Input 2

10 500000
1 100000
1 100000
1 100000
1 100000
1 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000

Sample Output 2

1



Sample input:
3 4
1 1
2 2
3 3


Sample output:
3

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
temp={}
a=[0]*n
for i in range(n):
  at,bt=map(int,input().split())
  a[i]=at
  temp[at]=temp.get(at, 0)+bt
a=list(set(a))
a.sort()
cnt=0
for i in range(n):
  cnt=cnt+temp[a[i]]
  if cnt>=k:
    print(a[i])
    break

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,K = I()
L = [l() for _ in range(N)]
L.sort()
for i in range(N):
    K -= L[i][1]
    if K <= 0:
        print(L[i][0])
        exit()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N,K = list(map(int,input().split()))
count = {}
for i in range(N):
    a,b= list(map(int,input().split()))
    if a in count:
        count[a] += b
    else:
        count[a] = b
ct = sorted(count.items())

for i in range(len(ct)):
    if ct[i][1] >= K:
        print(ct[i][0])
        exit()
    else:
        K -= ct[i][1]

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda x: x[0])
sm = 0
for a, b in ab:
    sm += b
    if sm >= k:
        print(a)
        break

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
arr = []
for i in range(n):
    a, b = map(int, input().split())
    arr.append([a,b])
arr.sort()
s = 0
for i in range(n):
    s+=arr[i][1]
    if s >= k:
        print(arr[i][0])
        exit()
print(arr[-1][0])

Submission status: Accepted

Solution code:
from collections import defaultdict
import collections
import sys
input = sys.stdin.readline

n, K = [int(w) for w in input().split()]
dd = collections.defaultdict(int)

for i in range(n):
    a, b = [int(w) for w in input().split()]
    dd[a] += b

s_dd = sorted(dd.items(), key=lambda x: x[0])

i = 0
ans = 0
for k, v in s_dd:
    i += v
    if i >= K:
        ans = k
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N, K = mi()
    a, b = i2(N)
    d = defaultdict(int)
    for i in range(N):
        d[a[i]] += b[i]
    d = [(k, v) for k, v in d.items()]
    d.sort()
    s = 0
    for k, v in d:
        s += v
        if s >= K:
            print(k)
            return



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = [int(i) for i in input().split()]


kaneko = []

for i in range(N):
    a,b = [int(i) for i in input().split()]
    c = [a,b]
    kaneko.append(c)

kaneko = sorted(kaneko)
sum = 0

for i in range(N):
    sum += kaneko[i][1]
    if sum >= K:
        print(kaneko[i][0])
        break

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n, k = LI()
d = defaultdict(int)
for _ in range(n):
    a, b = LI()
    d[a] += b

d = sorted(d.items(), key=lambda x: x[0])
# print(d)
i = 0
ans = 1
cnt = 0
while cnt < k:
    ans = d[i][0]
    cnt += d[i][1]
    i += 1
print(ans)

Submission status: Accepted

Solution code:
n , k = map(int,input().split())
hoge = [list(map(int,input().split())) for _ in range(n)]
hoge.sort()
sushi = 0
for i in range(n):
  sushi += hoge[i][1]
  if sushi >= k:
    print(hoge[i][0])
    break

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,k = readInts()
dic = defaultdict(int)
d = set()
for i in range(n):
    a,b = readInts()
    d.add(a)
    dic[a] += b
d = sorted(list(d))
ans = 0
for v in d:
    if ans + dic[v] >= k:
        print(v)
        exit()
    ans += dic[v]

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
A.sort()
for i in range(N):
    if K>A[i][1]:
      K -= A[i][1]
    else:
      ans = A[i][0]
      break
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
cnt = 0
i = 0
while i<N:
    a,b = A[i]
    if cnt+b<=K:
        cnt += b
    else:
        break
    i += 1
if cnt==K:
    print(A[i-1][0])
else:
    print(A[i][0])

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(n)])
for a,b in ab:
    if b <= k:
        k -= b
    else:
        k = 0
    if k == 0:
        print(a)
        exit()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
cnt = 0
num = []
for i in range(n):
    a,b = map(int,input().split())
    num.append((a,b))
num.sort()
for i in range(n):
    cnt += num[i][1]
    if cnt >= k:
        print(num[i][0])
        exit()

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=[LI() for i in range(n)]
lis.sort()
sm=[]
for i in range(n):
    sm.append(lis[i][1])
sm=list(accumulate(sm))
for i in range(n):
    if sm[i]>=k:
        print(lis[i][0])
        break

Submission status: Accepted

Solution code:
num=[]
n,k=map(int,input().split())
for i in range(n):
    num.append(list(map(int,input().split())))
str= lambda val: val[0]
num.sort(key=str)
num1=0
for i in range(n):
    num1+=num[i][1]
    if num1>=k:
        ans=num[i][0]
        break
print(ans)

Submission status: Accepted

Solution code:
N,K = [int(i) for i in input().split()]
dic = {}
sum = 0

for i in range(N):
    a,b = [int(i) for i in input().split()]
    if a in dic:
        dic[a] += b
    else:
        dic[a] = b

dic = sorted(dic.items())

for i in range(len(dic)):
    sum += dic[i][1]
    if K <= sum:
        print(dic[i][0])
        break

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

n,k=map(int,input().split())
lst=[0]*100001

for i in range(n):
    a,b=map(int,input().split())
    lst[a]+=b

for i in range(100001):
    k-=lst[i]
    if k<=0:
        print(i)
        break

Submission status: Accepted

Solution code:
import heapq
n,k = map(int,input().split())
ab = [0]*n
lis = []
for i in range(n):
    a,b = map(int,input().split())
    lis.append([a,b])
lis.sort(key= lambda val : val[0])
c = 0
for a,b in lis:
    if k <= c+b:
        ans = a
        break
    else:
        c += b
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
dic = {}
for i in range(n):
  a, b = map(int, input().split())
  dic.setdefault(a, 0)
  dic[a] += b
lst = sorted(list(dic.items()))
for tpl in lst:
  if k > tpl[1]:
    k -= tpl[1]
  else:
    print(tpl[0])
    exit()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a, b = [], []

for i in range(N):
    a0, b0 = map(int, input().split())
    a.append(a0)
    b.append(b0)

a, b = zip(*sorted(zip(a, b)))
num = 0
for i in range(N):
    num += b[i]
    if num >= K:
        print(a[i])
        break

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
c = defaultdict(int)

for i in range(n):
    a, b = MAP()
    c[a] = c[a] + b

d = sorted(c.items(), key=itemgetter(0))
reg = 0
for x in d:
    reg += x[1]
    if reg >= k:
        print(x[0])
        exit()

Submission status: Accepted

Solution code:

(n, k) = map(int, input().split())
(a, b) = zip(*[map(int, input().split()) for _ in range(n)])

cnt_dict = {}
for i in range(n):
    if a[i] not in cnt_dict.keys():
        cnt_dict[a[i]] = 0
    cnt_dict[a[i]] += b[i]

length = 0
for a_i in sorted(cnt_dict.keys()):
    length += cnt_dict[a_i]
    if length >= k:
        ans = a_i
        break

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [0] * N
for i in range(N):
  A[i] = list(map(int, input().split()))
  
A = sorted(A)
now = 0
for i in range(N):
  if now + A[i][1] >= K:
    print(A[i][0])
    quit()
  else:
    now += A[i][1]

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
lst=[0]*(10**5+1)
for i in range(n):
    a,b=map(int,input().split())
    lst[a]+=b

count=0
for i in range(10**5+1):
    count+=lst[i]
    if count>=k:
        print(i)
        break

Submission status: Accepted

Solution code:
def main4():
    lis = []
    n,k=map(int, input().split())
    for i in range(n):
        a,b = map(int, input().split())
        lis.append([a,b])
    lis.sort(key = lambda x:x[0])
    res = 0
    i=-1
    while(res < k):
        i+=1
        res += lis[i][1]
        if(res>=k):
            print(lis[i][0])
            break


if __name__ == '__main__':
    main4()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
dp=[0]*(10**5)
ans=0
for _ in range(N):
  a,b=map(int,input().split())
  dp[a-1]+=b
for j in range(len(dp)):
  if K<=ans+dp[j]:
    print(j+1)
    exit()
  ans+=dp[j]

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
dic = {}
for _ in range(N):
  a, b = map(int,input().split())
  if a in dic:
    dic[a] += b
  else:
    dic[a] = b
List = sorted(dic)
ans = 0
i = 0
while M > 0:
  M -= dic[List[i]]
  ans = List[i]
  i += 1
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
ab.sort()
C = 0
M = 0
for i in range(N):
    C += ab[i][1]
    if C >= K:
        print(ab[i][0])
        break

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
cnt = [0 for _ in range(10**5 + 10)]

for i in range(N):
    a, b = map(int, input().split())
    cnt[a] += b

res = 0
for i in range(len(cnt)):
    res += cnt[i]
    if res >= K:
        break
print(i)

Submission status: Accepted

Solution code:
import bisect

N, K = map(int, input().split())
A = []; B = [0]

for i in range(N):
    a, b = map(int, input().split())
    A.append([a, b])
A.sort()
for i in range(N):
    B.append(A[i][1] + B[i])

ans = bisect.bisect_left(B, K) - 1
print(A[ans][0])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 ** 9 + 7

# map(int, input().split())
# list(map(int, input().split()))

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

big_array = [0] * (10 ** 5 + 1)
for i in range(N):
    a, b = map(int, input().split())
    big_array[a] += b

count = 0
for i in range(1, 10 ** 5 + 1):
    count += big_array[i]
    if count >= K:
        print(i)
        break

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N, K = [int(x) for x in input().split(" ")]
    arr = []
    for _ in range(N):
        a, b = [int(x) for x in input().split(" ")]
        arr.append((a, b))
    arr.sort()

    k = 0
    for a, b in arr:
        if k + b < K:
            k = k + b
        else:
            print(a)
            break

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda i: i[0])
for i in range(n):
    k -= ab[i][1]
    if k <= 0:
        print(ab[i][0])
        exit()

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
d = {}
for _ in range(n):
  a,b = map(int, input().split())
  if a not in d: d[a] = b
  else: d[a] += b

t = 0
for i in sorted(d.items(), key=lambda x:x[0]):
  t += i[1]
  if t >= k:
    print(i[0])
    exit()

Submission status: Accepted

Solution code:
n,k = list(map(int, input().split()))
ab = sorted([tuple(map(int, input().split())) for _ in range(n)])
A,B = list(zip(*ab))

from itertools import accumulate
import bisect
print(A[bisect.bisect_left(list(accumulate(B)), k)])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
#print(ab)
ab.sort()
#print(ab)
for i in range(n):
  k = k-ab[i][1]
  if k <= 0:
    print(ab[i][0])
    exit()

Submission status: Accepted

Solution code:
N_kai, K_ban = map(int, input().split())

dic = {}

for i in range(N_kai):
    a, b_ko = map(int, input().split())
    
    if (a not in dic.keys()):
        dic[a] = b_ko
    else:
        dic[a] = dic[a] + b_ko

sorted_dic = sorted(dic.items(), key=lambda x: x[0])
number = 0

if (K_ban == 1):
    print(sorted_dic[0][0])
else:
    for i in range(len(sorted_dic)):
        number += sorted_dic[i][1]
        
        if (number >= K_ban):
            print(sorted_dic[i][0])
            break

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
n_list = [0 for i in range(10**5)]

for i in range(n):
    a, b = map(int,input().split())
    n_list[a-1] += b

temp = 0

for i in range(len(n_list)):
    temp += n_list[i]
    if temp >= k:
        print(i+1)
        break

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = sorted([(list(map(int, input().split()))) for i in range(n)])
i = 0

while True:
  if (k - a[i][1]) > 0:
    k -= a[i][1]
    i += 1
  else:
    print(a[i][0])
    break

Submission status: Accepted

Solution code:
NMAX = 100005
n,k = map(int,input().split())

array = [0] * NMAX

for i in range(n):
    a,b = map(int,input().split())
    array[a] += b

for i in range(1,NMAX,1):
    if k <= array[i]:
        print(i)
        exit()
    k -= array[i]

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin
input = stdin.readline
d = defaultdict(int)
n,k = map(int,input().split())
for _ in range(n):
    a,b = map(int,input().split())
    d[a]+=b
for key in sorted(d.keys()):
    v = d[key]
    k-=v
    if k <= 0:
        break
print(key)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
buf = sys.stdin.buffer


def main():
    n, k = map(int, buf.readline().split())
    AB = map(int, buf.read().split())

    count = defaultdict(int)
    for a, b in zip(AB, AB):
        count[a] += b

    idx = 0
    for num in sorted(count.keys()):
        idx += count[num]
        if idx >= k:
            print(num)
            break


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ab=sorted([list(map(int,input().split()))for i in range(n)])
c=0
for i in ab:
 a,b=i[0],i[1];c+=b
 if c>=k:exit(print(a))

Submission status: Accepted

Solution code:

url = "https://atcoder.jp//contests/abc061/tasks/abc061_c"
import heapq


def main():
    n,k = list(map(int, input().split()))
    dic = {}
    for _ in range(n):
        t = list(map(int, input().split()))
        dic.setdefault(t[0], 0)
        dic[t[0]] += t[1]
    dic_sorted = sorted(dic.items(), key=lambda x: x[0])
    count = 0
    for l in dic_sorted:
        count += l[1]
        if count >= k:
            print(l[0])
            exit()



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, k = map(int, readline().split())
ab = [list(map(int, readline().split())) for _ in range(n)]

ab.sort()

cnt = 0
for i in range(n):
    cnt += ab[i][1]
    if cnt >= k:
        print(ab[i][0])
        exit()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
l = [0]*(10**5+1)
for i in range(n):
    ai,bi = map(int,input().split())
    l[ai]+=bi
for index,i in enumerate(l):
    if i:
        k-=i
        if k<=0:
            break
print(index)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
D = dict()
for i in range(n):
    a, b = map(int, input().split())
    if a in D.keys():
        D[a] += b
    else:
        D[a] = b

D = sorted(D.items(), key=lambda x: x[0])
for d in D:
    if k <= d[1]:
        print(d[0])
        break
    else:
        k -= d[1]

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
C=[0]*(10**5+1)
for i in range(N):
    a,b=map(int,input().split())
    C[a]+=b
cnt=0
l=0
while cnt<K:
    l+=1
    cnt+=C[l]
print(l)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_ints(): return list(map(int, read().split()))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


N, K = read_ints()
AB = read_tuple(N)
AB.sort()

# めちゃくちゃセグ木と二部探したくなるけど線形探索で十分

now = 0  # i番目の要素をすべて考慮したとき何番目の数になるか
# 初めてK以上になったときの数が答え
for a, b in AB:
    now += b
    if now >= K:
        print(a)
        exit()

Submission status: Accepted

Solution code:
def readinput():
    n,k=list(map(int,input().split()))
    abList=[]
    for _ in range(n):
        a,b=list(map(int,input().split()))
        abList.append((a,b))
    return n,k,abList

def main(n,k,abList):
    hist=[0]*(10**5+1)
    for a,b in abList:
        hist[a]+=b
    sum=0
    for i in range(1,10**5+1):
        sum+=hist[i]
        if sum>=k:
            return i
    else:
        return 0

if __name__=='__main__':
    n,k,abList=readinput()
    ans=main(n,k,abList)
    print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(N)]
#print(lst)
#print(lst.sort())
lst.sort(key=lambda l:l[0])
#print(lst)

sm = 0
for x in lst:
    sm += x[1]
    #print(lst[i][1])
    if sm >= K:
        print(x[0])
        break

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A_MAX = 10**5
bkt = [0 for _ in range(A_MAX+1)]
for _ in range(n):
    a, b = map(int, input().split())
    bkt[a] += b
sum_count = 0
for i, cnt in enumerate(bkt):
    sum_count += cnt
    if sum_count >= k:
        print(i)
        break

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ab = {}
for _ in range(n):
    a, b = map(int, input().split())
    ab.setdefault(a, 0)
    ab[a] += b
keys = list(ab.keys())
keys.sort()
i = 0
for key in keys:
    i += ab[key]
    if i >= k:
        print(key)
        break

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = []
B = []

for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)

A = sorted(A)

ss = [0]*(N+1)
ss[0] = A[0][1]

for i in range(1, N):
    ss[i] = ss[i-1] + A[i][1]
    if ss[i-1] < K <= ss[i]:
        print(A[i][0])
        exit()
    else:
        pass

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(N)]
l.sort(key=lambda x: x[0])

cnt = 0
for x in l:
  cnt += x[1]
  if cnt >= K:
    print(x[0])
    break

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
num = [0]*(int(1e5)+1)
for _ in range(N):
  a,b=map(int,input().split())
  num[a] += b
for i in range(int(1e5)+1):
  K -= num[i]
  if K <= 0:
    print(i)
    break

Submission status: Accepted

Solution code:
N,K=map(int,input().split())

#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[0 for j in range(2)] for i in range(100010)]

for i in range(N):
    T=list(map(int,input().split()))
    S[T[0]][0]=T[0]
    S[T[0]][1]+=T[1]

#print(S)

for i in range(100010):
    if S[i][0]!=0:
        K-=S[i][1]
        if K<=0:
            print(S[i][0])
            exit()

Submission status: Accepted

Solution code:
N,K=[int(i) for i in input().split()]
R={}
for n in range(N):
    a,b=[int(i) for i in input().split()]
    R[a]=b+(R[a] if (a in R) else 0)
RR=sorted(list(R.keys()))
k=0
for ir in range(len(RR)):
    k+=R[RR[ir]]
    if k>=K:
      print(RR[ir])
      break

Submission status: Accepted

Solution code:
def resolve():
    N, K = [int(i) for i in input().split()]
    aabb = sorted([list(map(int, input().split())) for _ in range(N)])
    sumB = 0
    for a, b in aabb:
        sumB += b
        if sumB >= K:
            print(a)
            return


resolve()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())

d={}
for _ in range(n):
    a_i,b_i=map(int,input().split())
    if a_i in d:
        d[a_i]+=b_i
    else:
        d[a_i]=b_i


a=[]
b=[]

d=sorted(d.items(),key=lambda x: x[0])


prev=0
for key,value in d:
    a.append(key)
    b.append(prev+value)

    prev+=value


for j in range(len(b)):
    if k<=b[j]:
        break

print(a[j])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())

AB = [[] for _ in range(N)]

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

AB = sorted(AB)
mem = K
for ab in AB:
    a = ab[0]
    b = ab[1]
    mem -= b
    if mem <= 0:
        print(a)
        break

Submission status: Accepted

Solution code:
N, K = map(int, input().split())

A = [[] for _ in range(N)]
B = [[] for _ in range(N)]

for i in range(N):
    A[i], B[i] = map(int, input().split())

import numpy as np
Ind = np.argsort(A)

mem = K
for ind in Ind:
    mem -= B[ind]
    if mem <= 0:
        print(A[ind])
        break

Submission status: Accepted

Solution code:
def main():
    n,k=map(int,input().split())
    arr = []
    for _ in range(n):
        a,b=map(int,input().split())
        arr.append((a, b))
    arr.sort()
    for x, c in arr:
        if k <= c:
            print(x)
            break
        else:
            k -= c
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
l = [0]*100010
cnt = 0

for i in range(n):
    a, b = map(int, input().split())
    l[a] += b

for i in range(100010):
    cnt += l[i]
    if k <= cnt:
        print(i)
        exit()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
Ans = [0] * (10**5 + 10)

for _ in range(N):
    a, b = map(int, input().split())
    Ans[a] += b

for i, ans in enumerate(Ans):
    K -= ans
    if K <= 0:
        print(i)
        exit()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
num = (10**5+1)*[0]
tot = 0

for n in range(N):
  a,b=map(int,input().split())
  num[a]+=b 

for n in range(10**5+1):
  tot+=num[n]
  if K<=tot:
    print(n)
    break

Submission status: Accepted

Solution code:
'''
Accepted    　:No
difficult   　: 
ペナルティ　  　:5分
実際の回答時間  :分
WAの回数　     :回
合計時間　　  　:分
'''

def myAnswer(N:int,K:int,A:list,B:list) -> int:
   dic = {}
   for a,b in zip(A,B):
      if a in dic.keys():
         dic[a] += b
      else:
         dic[a] = b
   total = 0
   for a,b in sorted(dic.items()):
      total += b
      if K <= total:
         return a

def modelAnswer():
   return
def main():
   N,K = map(int,input().split())
   A = []
   B = []
   for _ in range(N):
      a,b = map(int,input().split())
      A.append(a)
      B.append(b)
   print(myAnswer(N,K,A,B))
if __name__ == '__main__':
   main()

Submission status: Accepted

Solution code:
a=list(map(int, input().split()))
xy=[map(int, input().split()) for l in range(a[0])]
x, y=[list(i) for i in zip(*xy)]
set=[[0 for j in range(2)] for i in range(a[0])]
num=0
for ele in x:
    set[num][0]=x[num]
    set[num][1]=y[num]
    num+=1
set.sort()
num=0
while a[1]>0:
    a[1]=a[1]-set[num][1]
    num+=1
print(set[num-1][0])

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


N, K = map(int, input().split())
ab = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    ab.append(tmp)
ab.sort()

cnt = 0
for i in range(N):
    cnt += ab[i][1]
    if cnt >= K:
        print(ab[i][0])
        exit(0)

Submission status: Accepted

Solution code:
from collections import defaultdict

N,K=map(int,input().split())
d=defaultdict(int)
for i in range(N):
    a,b=map(int,input().split())
    d[a]+=b

d=d.items()
d=sorted(d,key=lambda x:x[0])

cnt=0
for key,value in d:
    cnt+=value
    if cnt>=K:
        print(key)
        exit()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
di = [0]*(10**5)
for i in range(n):
    a,b = map(int,input().split())
    di[a-1] += b
q = 0
p = 0
while True:
    q += di[p]
    if k <= q:
        print(p +1)
        break
    p += 1

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = map(int, input().split())
ab = [None]*n
for i in range(n):
    ab[i] = list(map(int, input().split()))
ab.sort()
for a,b in ab:
    k -= b
    if k<=0:
        print(a)
        break

Submission status: Accepted

Solution code:
from operator import itemgetter
n,k = map(int,input().split())
count = 0
ans = 0
a = [list(map(int,input().split())) for i in range(n)]
number = sorted(a, key = lambda x: x[0])

for i in range(n):
    count += number[i][1]
    if count >= k:
        ans = number[i][0]
        break
    
print(ans)

Submission status: Accepted

Solution code:
N,K=[int(i) for i in input().split(" " )]
s = []
for i  in  range(N):
  s.append([int(ii) for ii in input().split(" ")])

s.sort( key=lambda x: x[0])  
countPush = 0
for i in s:
   countPush += i[1]
   if(countPush >= K ):
     print(i[0])
     break

Submission status: Accepted

Solution code:
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
n, k = map(int, input().split())
x = [0]*((10**5)+1)
for i in range(n):
    a, b = map(int, input().split())
    x[a] += b
y = 0
for i in range(len(x)):
    y += x[i]
    if y >= k:
        print(i)
        exit()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = [list(map(int, input().split())) for i in range(N)]
a.sort()
ans = a[0][0]
b = a[0][1]
i = 1
while b < K:
  ans = a[i][0]
  b += a[i][1]
  i += 1
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
l = [0 for i in range(100001)]
num_count = 0
n = 0
for j in range(N):
    a, b = map(int, input().split())
    l[a] += b
for k in l:
    num_count += k
    if num_count >= K:
        print(n)
        break
    else:
        n += 1

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
cnt=0
lst=sorted([list(map(int,input().split())) for _ in range(n)])
#print(lst)
i=0
while cnt<m:
    cnt+=lst[i][1]
    if cnt<m:
        i+=1
print(lst[i][0])

Submission status: Accepted

Solution code:
from collections import defaultdict

n,k = map(int,input().split())
dct = defaultdict(int)
for _ in range(n):
    a,b=map(int,input().split())
    dct[a]+=b
dct = sorted(dct.items())
now=0
for tpl in dct:
    now+=tpl[1]
    if now>=k:
        print(tpl[0])
        break

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
lst=sorted([list(map(int,input().split())) for _ in range(n)])

cnt=0
sm=0
for i in range(n):
    if sm<k:
        cnt+=1
    sm+=lst[i][1]
print(lst[cnt-1][0])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())

backet=[0]*(10**5+1)
for i in range(n):
    a,b=map(int,input().split())
    backet[a]+=b

for i in range(1,10**5+1):
    if backet[i] >= k:
        print(i)
        exit()
    k-=backet[i]

Submission status: Accepted

Solution code:
(N, K), *AB = [list(map(int, s.split())) for s in open(0)]
for a, b in sorted(AB):
    K -= b
    if K <= 0:
        print(a)
        break