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())

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

l = sorted(l, key = lambda x:x[0])
cnt = 0    
for a,b in l:
    cnt += b
    
    if cnt >= k:
        print(a)
        break

Submission status: Accepted

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

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

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

AB = sorted(AB, key = lambda x:x[0])
amount = 0
for a,b in AB:
  amount += b
  if amount >= K:
    print(a)
    break

Submission status: Accepted

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

# a number counter that can appear on a number line.
n_counter = [0 for _ in range(10**5 + 1)]
for i in range(N):
  a, b = map(int, input().split())
  n_counter[a] += b

# ask for K.
n_sum = 0
for i, n in enumerate(n_counter):
  n_sum += n
  if n_sum >= K:
    print(i)
    break

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
d=[0]*(10**5+1)
for i in range(n):
  a,b=map(int,input().split())
  d[a]+=b
for i in range(10**5+1):
  if d[i]>=k:
    print(i)
    break
  else:k-=d[i]

Submission status: Accepted

Solution code:
from collections import Counter
n, k = map(int, input().split())

c = Counter()
for _ in range(n):
    a, b = map(int, input().split())
    c[a] += b
c = sorted(c.items(), key=lambda x: x[0])

for i, v in c:
    k -= v
    if k <= 0:
        print(i)
        exit()

Submission status: Accepted

Solution code:
n,k=[int(x) for x in input().rstrip().split()]
dic={}
for i in range(n):
  a,b=[int(x) for x in input().rstrip().split()]
  if a not in dic:
    dic[a]=b
  else:
    dic[a]+=b

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

now=0
for i,v in dic:
  now+=v
  if k<=now:
    print(i)
    break

Submission status: Accepted

Solution code:
n,k=[int(x) for x in input().rstrip().split()]
dic={}
for i in range(n):
  a,b=[int(x) for x in input().rstrip().split()]
  if a not in dic:
    dic[a]=b
  else:
    dic[a]+=b

dic=sorted(dic.items())

now=0
for i,v in dic:
  now+=v
  if k<=now:
    print(i)
    break

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,k = map(int,ipt().split())
    hq = []
    for _ in range(n):
        a,b = map(int,ipt().split())
        hpq.heappush(hq,(a,b))
    while True:
        hqa,hqb = hpq.heappop(hq)
        if hqb < k:
            k -= hqb
        else:
            print(hqa)
            exit()
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

n = 0
for i in range(10**5):
    n += d[i+1]
    if n >= K:
        print(i+1)
        exit()

Submission status: Accepted

Solution code:
import sys
import itertools
import copy
from collections import defaultdict

input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N, K = MI()
    index = 0
    d = defaultdict(int)
    for i in range(N):
        a, b = MI()
        d[a] += b
    d = sorted(d.items(), key=lambda x:x[0])
    for i in d:
        index += i[1]
        if index >= K:
            print(i[0])
            sys.exit()
        
        
main()

Submission status: Accepted

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

ab = sorted([list(map(int, input().split())) for _ in range(n)])
cnt = 0
for i in ab:
    cnt += i[1]
    if cnt >= k:
        print(i[0])
        exit(0)

Submission status: Accepted

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

ab = [list(map(int, input().split())) for _ in range(n)]
s_ab = sorted(ab, key=lambda x: x[0])
cnt = 0
ans = -1
for i in s_ab:
    cnt += i[1]
    if cnt >= k:
        ans = i[0]
        break
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
dict = {}
ans = 0

for i in range(n):
  a,b = map(int,input().split())
  if a not in dict:
    dict[a] = b
  else:
    dict[a] += b
    
dic = sorted(dict.items())


for key,v in dic:
  ans += v
  if ans >= k:
    print(key)
    exit()

Submission status: Accepted

Solution code:
def answer(arr, k):
    arr = sorted(arr, key=lambda a:a[0])
    for a, b in arr:
        if k > b:
            k -= b
        else:
            return a

n, k = map(int, input().split())
arr = []
for i in range(n):
    a, b = map(int, input().split())
    arr.append((a, b))
print(answer(arr, k))

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(N)]
M = {}
for ab in AB:
    if ab[0] in M:
        M[ab[0]] += ab[1]
    else:
         M[ab[0]] = ab[1]
tmp = 0
keys = sorted(M.keys())
if M[keys[0]] >= K:
    print(keys[0])
    exit()
for i in range(1,len(keys)):
    M[keys[i]] = M[keys[i]]+M[keys[i-1]]
    if M[keys[i-1]] < K <= M[keys[i]]:
        print(keys[i])
        exit()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jun  5 16:50:04 2020

@author: NEC-PCuser
"""

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

ab_list.sort()


count = 0
for i in range(0, N):
    count += ab_list[i][1]
    
    if (count >= K):
        print(ab_list[i][0])
        break

Submission status: Accepted

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

ab = [[int(i) for i in input().split()] for _ in range(N)]

length = 0
sorted_ab = sorted(ab, key=lambda x:x[0])

for x in sorted_ab:
    length += x[1]
    if length >= K:
        output = x[0]
        break
    
print(output)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
length = 0
for x in sorted(ab, key=lambda x: x[0]):
    length += x[1]
    if length >= k:
        print(x[0])
        break

Submission status: Accepted

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

A = [0] * (10**5)

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

cnt = 0
while K > 0:
    K -= A[cnt]
    cnt += 1
print(cnt)

Submission status: Accepted

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

dic= {}
for i in range(n):
  a,b = list(map(int,input().strip().split()))
  if a in dic:
    dic[a] += b
  else:
    dic[a] = b

arr = sorted(dic.items())
leng = 0
for i in arr:
  leng += i[1]
  if leng >= k:
    print(i[0])
    exit()

Submission status: Accepted

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

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

ab.sort(key=lambda x: x[0])

cnt = 0
for a, b in ab:
    if cnt <= k <= cnt+b:
        print(a)
        exit()
    cnt += b

Submission status: Accepted

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

ab.sort()
now = 0
count = 0
for i in range(N):
  now = ab[i][0]
  count += ab[i][1]
  if count >= K:
    print(now)
    break

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

cnt = 0
d = []
for _ in range(N):
    a,b = map(int,input().split())
    d.append((a,b))

for i,j in sorted(d):
    cnt += j
    if cnt >= K:
        print(i)
        break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ab = [[int(i) for i in input().split()] for i in range(N)]
ab.sort()
check = 0
for a, b in ab:
    check += b
    if check >= K:
        print(a)
        break

Submission status: Accepted

Solution code:
N, K = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

from collections import defaultdict
d = defaultdict(lambda: 0)		#初期値を「-1」にする

for n in range(N):
  k, v = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7
  d[k] += v

cnt=0
for k, v in sorted(d.items(), key=lambda x: x[0]):
  cnt += v
  if cnt >= K:
    print(k)
    exit(0)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    n, k = list(map(int, input().split()))
    d = defaultdict(int)
    for _ in range(n):
        a, b = list(map(int, input().split()))
        d[a] += b
    A = sorted(d.items(), key = lambda x: x[0])
    count = 0
    for a in A:
        count += a[1]
        if count >= k:
            print(a[0])
            exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

dic2 = sorted(dic.items())
c = 0
for i in dic2:
    c += i[1]
    if c >= k:
        print(i[0])
        exit()

Submission status: Accepted

Solution code:
def main():
    M = 10 ** 5
    N, K = list(map(int, input().split(' ')))
    count = [0 for _ in range(M + 1)]
    for _ in range(N):
        a, b = list(map(int, input().split(' ')))
        count[a] += b
    ans = 0
    while K > 0:
        ans += 1
        K -= count[ans]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

while S < K:
  S+= array[i]
  i+= 1
  
print(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])
start = 1
end = 0
for i in range(n):
    a, b = ab[i]
    end += b
    if start <= k <= end:
        print(a)
        exit()
    start += b

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    L = [lmi() for _ in range(n)]
    L.sort(key=lambda x: x[0])
    for a, b in L:
        if k > b:
            k -= b
        else:
            print(a)
            exit()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
cnt = 0
lst = []
for _ in range(n):
    a,b = map(int, input().split())
    lst.append((a,b))
lst.sort()
for val in lst:
    cnt += val[1]
    if cnt >= m:
        print(val[0])
        break

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(n)]
L = sorted(L, key=lambda x: x[0])
s = 0
i = 0
while s < k:
    s += L[i][1]
    i += 1
print(L[i-1][0])

Submission status: Accepted

Solution code:
_,k,*l=map(int,open(0).read().split())
for a,b in sorted(zip(*[iter(l)]*2)):
 k-=b
 if k<1:print(a);exit()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N, K = getNM()
parent = []
for i in range(N):
    a, b = getNM()
    parent.append((a, b))
parent.sort(key = lambda int: int[0])

A = []
B = []
for a, b in parent:
    A.append(a)
    B.append(b)
alta = [0]
for i in range(N):
    alta.append(alta[i] + B[i])

index = bisect_left(alta, K)
print(A[index - 1])

Submission status: Accepted

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

Submission status: Accepted

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

cnt = 0
for key, val in lst:
  cnt += val
  if cnt >= k:
    print(key)
    break

Submission status: Accepted

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

arr = [list(map(int, input().split())) for _ in range(n)]
arr.sort()

cnt = 0
for a, b in arr:
    cnt += b
    if cnt >= k:
        ans = a
        break

print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
AB =[]
for n in range(N):
    a,b = map(int,input().split())
    AB.append([a,b])
AB.sort(key=lambda x:x[0])
cnt = 0
for i,a in enumerate(AB):
    if cnt < K:
        cnt +=a[1]
    if cnt >=K:
        print(a[0])
        exit()

Submission status: Accepted

Solution code:
N, M = input().strip().split()
N, M = [int(N), int(M)]

# 2次元配列
ab = sorted(list(map(int, input().split())) for _ in range(N))
c=0
for a,b in ab:
    c+=b
    if c>=M:
        print(a)
        break

Submission status: Accepted

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

count = 0
for a, b in ab:
    count += b
    if count >= k:
        print(a)
        break

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
A=[]
tmp=k
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A.sort(key=lambda x:x[0])
for i in range(n):
    tmp-=A[i][1]
    if tmp<=0:
        print(A[i][0])
        sys.exit()

Submission status: Accepted

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

for i in AB:
    a = i[0]
    b = i[1]
    
    k -= b
    
    if k < 1:
        print(a)
        break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
L = []
for _ in range(N):
    L.append(list(map(int, input().split())))
L = sorted(L, key=lambda x: x[0])

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

Submission status: Accepted

Solution code:
n,k = list(map(int,input().rstrip().split()))
array = []
for _ in range(n):
    array.append(list(map(int,input().strip().split())))
array.sort()

def find(ar,k):
    count = 0
    for a in ar:
        if count < k and k <= count+a[1]:
            return a[0]
        else:
            count += a[1]
print(find(array,k))

Submission status: Accepted

Solution code:
import fractions
import sys
from functools import reduce
import collections
import time
input = sys.stdin.readline


def main():
    n, k = input_list()
    total = 0
    a_map = {}
    for _ in range(n):
        num, count = input_list()
        if num in a_map:
            a_map[num] += count
        else:
            a_map[num] = count
    sa_map = sorted(a_map.items(), key=lambda x: x[0])

    for num, count in sa_map:
        total += count
        if k <= total:
            print(num)
            break
    # 2 3 3 3 4 4 4

def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))


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


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,K = IL()
d = ILL(N)
d.sort(reverse=True)
count = 0
while True:
  a,b = d.pop()
  count += b
  if count>=K:
    PE(a)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
ab = sorted(ab, key=lambda x: x[0])
ban = 0
for a, b in ab:
    ban += b
    if ban >= K:
        print(a)
        break

Submission status: Accepted

Solution code:

from collections import OrderedDict
result = OrderedDict()
N, K = map(int, input().split())
for i in range(N):
    a,b = map(int, input().split())
    if a in result:
        result[a] += b
    else:
        result[a] = b
result = sorted(result.items())
for k,v in result:
    if K > v:
        K -= v
    else:
        print(k)
        exit()

Submission status: Accepted

Solution code:
import bisect
n, k = map(int, input().split())
ab = sorted(map(lambda x: (int(x[0]), int(x[1])), [(input().split()) for _ in range(n)]))
cnt = []
s = 0
for i in range(n):
    cnt.append(ab[i][1] + s)
    s += ab[i][1]
# print(cnt)

print(ab[bisect.bisect_left(cnt, k)][0])

Submission status: Accepted

Solution code:
from collections import OrderedDict
result = OrderedDict()
N, K = map(int, input().split())
for i in range(N):
    a,b = map(int, input().split())
    if a in result:
        result[a] += b
    else:
        result[a] = b

result = sorted(result.items())
for k,v in result:
    if K > v:
        K -= v
    else:
        print(k)
        exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
'''
data = [10 ** 9]
for i in range(n):
    a, b = map(int, input().split())
    temp = [a] * b
    data.extend(temp)

rev = sorted(data)
#rev = data.reverse() > 大きい順
ans = rev[k - 1]
print(ans)

>最大で（１０*＊１０）サイズリストになる。

バケツソートが必要。
（出現回数を格納したリストから、答えを出す。）
'''

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, K = map(int, input().split())
a = defaultdict(int)
for i in range(N):
  num, length = map(int, input().split())
  a[num] += length
num = list(a.keys())
num.sort()
cnt = 0
for i in range(len(num)):
  cnt += a[num[i]]
  if cnt >= K:
    break
print(num[i])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
counts = dict()
for i in range(N):
    a, b = map(int, input().split())
    counts.setdefault(a, 0)
    counts[a] += b

for i in range(10**5+1):
    a = counts.get(i)
    if a is not None:
        if K <= a:
            break
        K -= a
print(i)

Submission status: Accepted

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

for i in range(10**5+1):
    if (K <= count[i]):
        break
    K -= count[i]
print(i)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split());i=0;a=sorted(list(map(int,input().split()))for _ in[0]*n)
while k>0:k-=a[i][1];i+=1
print(a[~-i][0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    l=[]
    for i in range(N):
        l.append(tuple(map(int,input().split())))
    l.sort(key=lambda t:t[0])
    for a,b in l:
        K-=b
        if K<=0:
            print(a)
            exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)
N, K = map(int, input().split())
for i in range(N):
    a, b = map(int, input().split())
    d[a] += b
for k, v in sorted(d.items()):
    K -= v
    if K <= 0:
        print(k)
        break

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
ab_list = [list(map(int,input().split())) 
           for nesya in range(n)]
ab_list.sort()
s = k
for ab in ab_list:
  s -= ab[1]
  if s > 0:
    pass
  else:
    print(ab[0])
    break

Submission status: Accepted

Solution code:
n , k = map(int,input().split())
p = {}
for i in range(n):
    a , b = map(int,input().split())
    p[a] = p.get(a,0) + b

ans = sorted(p.items())
cou = 0
for i , j in ans:
    cou += j
    if cou >= k:
        print(i)
        exit()

Submission status: Accepted

Solution code:
from collections import defaultdict

def solve():
    N, K = map(int, input().split())
    d = defaultdict(int)
    for _ in range(N):
        a, b = map(int, input().split())
        d[a] += b
        
    for k in sorted(d.keys()):
        K -= d[k]
        if K <= 0:
            return k
        
print(solve())

Submission status: Accepted

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

abb = sorted(ab)
temp =0

for i in range(n+1):
    if temp < k:
        temp += abb[i][1]
    else:
        print(abb[i-1][0])
        exit()

Submission status: Accepted

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

AB = []
for _ in range(N):
    ai, bi = map(int, input().split())
    AB.append((ai,bi))

AB.sort()

memo = {}
len_arr = 0

for ai, bi in AB:
    len_arr += bi
    memo[len_arr] = ai

len_arr_list = sorted(memo.keys())

for boundary in len_arr_list:
    if K <= boundary:
        print(memo[boundary])
        break

Submission status: Accepted

Solution code:
def invr():
    return(map(int, input().split()))


n, k = invr()
arr = []
d = dict()
for i in range(n):
    a, b = invr()
    if a in d:
        d[a] += b
    else:
        d[a] = b
        arr.append(a)
arr = sorted(arr)
pos = 0
for i in arr:
    pos += d[i]
    if pos >= k:
        print(i)
        break

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = []
for i in range(N):
    a,b = map(int, input().split())
    A.append((a,b))
A.sort()
for i in range(N):
    K -= A[i][1]
    if K <= 0:
        print(A[i][0])
        exit()