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:
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    else:print("No")
    exit(0)


def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)

#n = ip()                                     #入力整数1つ
n,k= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#v=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
a = []
for i in range(n):
    a.append([int(i) for i in input().split()])
p = -1
a.sort()
while k>0:
    p+=1
    k-=a[p][1]
print(a[p][0])

Submission status: Accepted

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

l = []
for i in range(N):
    a, b = map(int, input().split())
    heapq.heappush(l, (a, b))

k = 0
while K > k:
    a, b = heapq.heappop(l)
    k += b

print(a)

Submission status: Accepted

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

n = 0
for i,x in enumerate(l):
    n+=x
    if n>=k:
        print(i)
        break

Submission status: Accepted

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

o = [0]*(100001)
for i in range(N):
    a,b = map(int,input().split(" "))
    o[a] += b

for i in range(100001):
    a = min(K,o[i])
    if a == K:
        print(i)
        exit()
    K -= a

Submission status: Accepted

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

sumb = 0
for n in nums:
    sumb += n[1]
    if sumb >= K:
        print(n[0])
        break

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
# import statistics
import bisect
import copy
import fractions
import math
import pprint
# for debug
pp = pprint.PrettyPrinter(width = 150)
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))
def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]
def dfs(v):
    # ノードに訪れた
    visited[v] = True
    for v2 in range(n):
        if graph[v][v2] == False:  # そもそもvとv2が辺でつながっていない
            continue
        if visited[v2] == True:  # もう見た
            continue
        dfs(v2)


n, k = MI()
nums = sorted([LI() for _ in range(n)])
cnt = 0
for num, kosuu in nums:
    if cnt + kosuu < k:
        cnt += kosuu
    else:
        print(num)
        exit()

Submission status: Accepted

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

ab = sorted(ab)

s = 0
ans =ab[0][0]

for i, j in enumerate(ab):
  s += j[1]
  if s >= K:
    ans = ab[i][0]
    break
  else:
    ans = j[0]
  
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
array = [0]*(10**5+1)
for _ in range(N):
    a, b = map(int, input().split())
    array[a] += b
ans = 0
for i in range(10**5+1):
    K -= array[i]
    if K<= 0:
        ans = i
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def read_input():
    n, k = map(int, input().split())

    tups = []
    for i in range(n):
        tups.append(list(map(int, input().split())))

    return n, k, tups

def submit():
    n, k, tups = read_input()

    occurs = defaultdict(int)

    for tup in tups:
        occurs[tup[0]] += tup[1]

    nums = list(occurs.items())
    nums.sort(key=lambda x : x[0])

    count = 0
    for num in nums:
        if k <= count + num[1]:
            print(num[0])
            return
        count += num[1]



if __name__ == '__main__':
    submit()

Submission status: Accepted

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

n, k = map(int, input().split())
m = {}
ml = set()

for i in range(n):
    a, b = map(int, input().split())
    ml.add(a)
        
    if m.get(a):
        m[a] += b
    else:
        m[a] = b

mm = list(ml)
mm.sort()
for v in mm:
    if k > m[v]:
        k -= m[v]
    else:
        print(v)
        break

Submission status: Accepted

Solution code:
from collections import defaultdict

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

counter = 0
for a, b in sorted(c.items(), key=lambda x: x[0]):
    counter += b
    if counter >= K:
        break
print(a)

Submission status: Accepted

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

num = 0
for i in range(100005):
    if d[i] != 0:
        if num + d[i] >= K:
            print(i)
            break
        else:
            num += d[i]

Submission status: Accepted

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

items = dict()
for _ in range(n):
    ta, tb = map(int, input().split())
    if ta in items.keys():
        items[ta] += tb
    else:
        items[ta] = tb

items = sorted(items.items())

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

k=0
for i in range(len(a_list)):
    k+=a_list[i]
    if k >=K:
        break
print(i+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = [int(n) for n in input().split()]

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

    if a in l:
        l[a] += b
    else:
        l[a] = b

l = sorted(l.items())
c_ = 0
for a, b in l:
    c = c_ + b
    if c_ < k <= c:
        print(a)
        break
    else:
        c_ = c

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()
while K > 0:
    for _ab in ab:
        K -= _ab[1]
        if K <= 0:
            print(_ab[0])
            break

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
ab.sort(key=lambda x: x[0])
ab.insert(0, [0, 0])

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

for i in range(N):
    if ab[i][1] < K <= ab[i+1][1]:
        ans = ab[i+1][0]
        break

print(ans)

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n, k = f()
    pii = [[0,0] for i in range(n)]
    
    for i in range(n):
        x, y = f()
        pii[i][0] = x
        pii[i][1] = y

    pii = sorted(pii, key = lambda x: x[0])

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


solve()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
data = []
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if d.__contains__(a):
        d[a]+=b
    else:
        d[a] = b
data = list(d.items())
data.sort()

rank = 1

for x,cnt in data:
    if rank<=k and k<rank+cnt:
        print(x)
        break
    else:
        rank+=cnt

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,k=map(int,input().split())
a=[[] for i in range(n)]
for i in range(n):
    a[i]=list(map(int,input().split()))

a.sort(key=lambda x:x[0],reverse=True)
c=0
while c<k:
    x=a.pop()
    c+=x[1]
print(x[0])

Submission status: Accepted

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

ab.sort()

i = -1

while k>0:
    i+=1
    k-=ab[i][1]

print(ab[i][0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
for s,t in sorted([list(map(int,input().split()))for i in range(n)],key=lambda x:x[0]):
    if k>t:
        k-=t
    else:
        print(s)
        exit()

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 i in range(N):
    a = l[i][0]
    b = l[i][1]
    cnt += b
    if cnt >= K:
        print(a)
        break

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]
A.sort()
i=-1
count=0
ans=0
while count<k:
  i+=1
  ans=A[i][0]
  count+=A[i][1]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ab=[list(map(int, input().split())) for i in range(n)]
ab.sort()
count=0
ans=ab[0][0]
for i in range(n):
    if count+ab[i][1]<k:
        count+=ab[i][1]
    elif 0<=k-count<=ab[i][1]:
        ans=ab[i][0]
        break
print(ans)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,K=LI()
A=[]
B=[]
AB=[]
for i in range(N):
	a,b=LI()
	A.append(a)
	B.append(b)
	AB.append([a,b])
A=list(set(A))
A.sort()
counts={}
for a in A:
	counts[a]=0

for ab in AB:
	counts[ab[0]]+=ab[1]
if K<N/2:
	c=0
	for item in A:
		c+=counts.get(item)
		if c>=K:
			print(item)
			exit()
else:
	c=sum(B)
	for item in reversed(A):
		c-=counts.get(item)
		if c<K:
			print(item)
			exit()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=[0]*100001
for i in range(n):
    a,b=map(int,input().split())
    l[a]+=b
x=0
for i in range(100001):
    x+=l[i]
    if x>=k:break
print(i)

Submission status: Accepted

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

for i in range(n):
  a,b = map(int, input().split())
  if a in array: #キーがある場合
    array[a] += b
  else:
    array[a] = b
    
#  キーの順番でソートする
array_sorted = sorted(array.items())

ans = 0
cnt = 0
# k番目が何かを確認する
for elem in array_sorted:
  cnt += elem[1]
    
  if cnt >= k:
    #ans = key
    print(elem[0])
    break

Submission status: Accepted

Solution code:
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n, k = nm()
lis = [nl() for _ in range(n)]
lis.sort()
count = 0
for i in range(n + 1):
    if count >= k:
        print(lis[i - 1][0])
        exit()
    count += lis[i][1]

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
N,K=I()
AB=sorted([I()for _ in[0]*N])
s=0
for a,b in AB:
  if s+b>=K:print(a);break
  s+=b

Submission status: Accepted

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

Submission status: Accepted

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

nums = []
for i in range(0,N):
    ab = list(map(int,input().split()))
    nums.append(ab)

nums = sorted(nums,key = lambda x: x[0])
tmp = 0
index = 0
for i in range(0,N):
    tmp += nums[i][1]
    if tmp >= K:
        index = i
        break

print(nums[i][0])

Submission status: Accepted

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,K = (int(_) for _ in input().split())
    dict = {}
    ans = 0
    for i in range(N):
        s1,s2 = (int(_) for _ in input().split())
        if s1 not in dict:
            dict[s1] = s2
        else:
            dict[s1] += s2
    index = 0
    for k,v in sorted(dict.items()):
        index += v
        if(index >= K):
            ans = k
            break
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#import math
#n=int(input())
#li=input().split()
#n=int(input())
#S=input()

ab=[0]*(10**5+1)
lis=list(map(int,input().split()))
for i in range(lis[0]):
    t=list(map(int,input().split()))
    ab[t[0]]+=t[1]

ans=0
i=1
count=0
while count<lis[1]:
    count+=ab[i]
    ans=i
    i+=1

print(ans)

Submission status: Accepted

Solution code:
#14:59
#復習必要
#hashっぽい
N, K = map(int, input().split())

l = [0] * (10 ** 5 + 1)
for i in range(N):
    a, b = map(int, input().split())
    l[a] += b
cnt = 0
for i in range(1, 10 ** 5 + 1):
    cnt += l[i]
    if cnt >= K:
        print(i)
        break

Submission status: Accepted

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

AB = sorted(AB, key=lambda x: x[0])
for i in range(N):
    if i > 0:
        AB[i][1] += AB[i-1][1]
    if K <= AB[i][1]:
        print(AB[i][0])
        break

Submission status: Accepted

Solution code:
import sys
fastinput=sys.stdin.readline
N,K=map(int,fastinput().split())
data=[[int(j) for j in fastinput().split()] for k in range(N)]
ab=sorted(data,key=lambda x:x[0])
number=0
for a,b in ab:
    number+=b
    if number>=K:
        print(a)
        break

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
dict = {}
for i in range(N):
  a,b = map(int,input().split())
  if(a in dict): dict[a] += b
  else: dict[a] = b

count = 0
ans = 0
for k, v in sorted(dict.items()):
   count += v
   if(count >= K): 
    ans = k
    break
print(ans)

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
for i in range(1,len(l)):
    l[i] += l[i-1]
    if k<=l[i]:
        print(i)
        exit()

Submission status: Accepted

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

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

rules = sorted(rules, key=lambda x: x[0])
for rule in rules:
    K -= rule[1]
    if K <= 0:
        print(rule[0])
        break

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

AB.sort()
if AB[0][1] >= K:
    ans = AB[0][0]
else:
    for i in range(1,N):
        AB[i][1] += AB[i-1][1]
        if AB[i][1] >= K:
            ans = AB[i][0]
            break
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
count = 0
ab = [list(map(int, input().split())) for _ in range(n)]
ab = sorted(ab)
i = 0
while count < k:
  a, b = ab[i]
  count += b
  i += 1
  if count >= k:
    print(a)
    break

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
L = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
num = 0
for a, b in L:
    num += b
    if K <= num:
        print(a)
        exit()

Submission status: Accepted

Solution code:
import numpy as np
 
N, K = [int(i) for i in input().split()]
ab = np.array(
  [[int(i) for i in input().split()] for _ in range(N)])
 
idx_ab = np.argsort(ab[:, 0])
ab = ab[idx_ab, :]

k_sum = 0
 
for record in ab:
  a = record[0]
  b = record[1]
  
  k_sum += b
  if k_sum >= K:
    print(a)
    break

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append((a, b))

    A = sorted(A, key=lambda x: x[0])

    cnt = 0
    for x in A:
        cnt += x[1]
        if cnt >= K:
            return x[0]


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
n,K=map(int,input().split());c={}
for i in range(n):
  a,b=map(int,input().split())
  if a in c:c[a]+=b
  else:c[a]=b
for k,v in sorted(c.items()):
  K-=v
  if K<=0:print(k);exit()

Submission status: Accepted

Solution code:
from sys import stdin

n, k = list(map(int, stdin.readline().split()))
ax = [0]*100001
c = 0
j = 0

for i in range(n):
    a, b = list(map(int, stdin.readline().split()))
    ax[a] += b

while c < k:
    c += ax[j]
    j += 1

print(j-1)

Submission status: Accepted

Solution code:
from operator import itemgetter
N, K = map(int, raw_input().split())
a = []
for i in range(N):
    a.append(map(int, raw_input().split()))
a.sort(key=itemgetter(0))
thre = 0
for i in a:
    thre += i[1]
    if thre >= K:
        print(i[0])
        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()
for i in range(n):
    if ab[i][1]>=k:
        print(ab[i][0])
        break
    else:
        k = k - ab[i][1]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = []
for i in range(N):
    a.append(list(map(int, input().split())))
a.sort()
sum = 0
for i, x in enumerate(a):
    sum += x[1]
    if sum >= K:
        print(a[i][0])
        break

Submission status: Accepted

Solution code:
import sys
N , K = map(int,input().split())
ablist = [list(map(int,input().split())) for _ in range(N)]
ablist.sort(key=lambda x: x[0])
for ab in ablist:
    K -= ab[1]
    if K <= 0:
        print(ab[0])
        sys.exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
number=[[int(i) for i in l.split()] for l in sys.stdin]
stack=[0]*(10**5+1)
for i in number:
  stack[i[0]]+=i[1]
acsum=[]
acSum=0
for i in stack:
  acSum+=i
  acsum.append(acSum)
def binary_search():
  ng=-1
  ok=10**5+1
  while abs(ng-ok)>1:
    mid=(ng+ok)//2
    if acsum[mid]>=k:
      ok=mid
    else:
      ng=mid
  return ok
print(binary_search())

Submission status: Accepted

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

for i,j in enumerate(arr):
    if j >= k:
        print(i)
        exit()

Submission status: Accepted

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

Submission status: Accepted

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

n,k = map(int,input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i],b[i] = map(int,input().split())

ab = [[0,0] for i in range(n)]

for i in range(n):
    ab[i] = [a[i],b[i]]

ab.sort()

cnt = 0

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

Submission status: Accepted

Solution code:
from sys import stdin
n, k = map(int, input().split())
nums = [list(map(int, stdin.readline().split())) for _ in range(n)]
nums.sort(key=lambda x:x[0])
i = 0
while True:
    k -= nums[i][1]
    if k <= 0:
        print(nums[i][0])
        break
    i += 1

Submission status: Accepted

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

l=0
for a, b in AB:
  l+=b
  if l>=K:
    print(a)
    exit()

Submission status: Accepted

Solution code:
arr = [0] * 100100
n,k = map(int,input().split())
for i in range(n):
    a,b = map(int,input().split())
    arr[a] += b
for i in range(100010):
    arr[i + 1] += arr[i]
for i,j in enumerate(arr):
    if j >= k:
        print(i)
        exit()

Submission status: Accepted

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

for k in range(N):
    a, b = map(int, input().split())
    num.append((a, b))

num = sorted(num)
cnt = 0
for i in num:
    cnt += i[1]
    if cnt >= K:
        print(i[0])
        break

Submission status: Accepted

Solution code:
from collections import defaultdict

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

counts = defaultdict(int)

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

for num in sorted(counts.keys()):
    K -= counts[num]
    if K <= 0:
        print(num)
        break

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,k, = map(int,input().split())
list = []
sum = 0
for i in range(n):
    a,b = map(int,input().split())
    list.append([a,b])

list.sort()
for i in range(n):
    sum = sum + list[i][1]
    if sum >= k:
        break
print(list[i][0])

Submission status: Accepted

Solution code:
def big_array(N: int, K: int, queries: list)->int:
    d = {}
    for a, b in queries:
        d.setdefault(a, 0)
        d[a] += b

    count = 0
    ans = 0
    for k, v in sorted(d.items()):
        count += v
        if K <= count:
            ans = k
            break
    return ans


if __name__ == "__main__":
    N = 0
    N, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(N)]
    ans = big_array(N, K, queries)
    print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
N,K = map(int,input().split())
c = [list(map(int,input().split())) for i in range(N)]
c.sort(key=itemgetter(0))
s = 0
for i in range(N):
    if s+c[i][1] < K:
        s += c[i][1]
    else:
        ans = c[i][0]
        break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

counter = 0
array1 = []

for i in range(N):
  counter += ab[i][1]
  if K <= counter:
    ans = ab[i][0]
    break

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
X=[0]*10**5
for _ in range(n):
    a,b=map(int,input().split())
    X[a-1]+=b
cnt=0
for i in range(10**5):
    cnt+=X[i]
    if cnt>=k:
        print(i+1)
        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))
    
B = []
for i in sorted(AB):
    B.append(i[1])
# print(B)
import numpy
B_res = numpy.cumsum(B)
# print(B_res)

from bisect import bisect_left,bisect_right
# print(bisect_left(B_res, K))
print(sorted(AB)[bisect_left(B_res, K)][0])

Submission status: Accepted

Solution code:
def two_dim_merge_sort(arr):##arrは二次元配列
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = two_dim_merge_sort(left)
    right = two_dim_merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return two_dim_merge(left, right)


def two_dim_merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i][0] <= right[r_i][0]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged



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

a = [0] * n
b = [0] * n

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

l = [0] * n

for i in range(0,n):
    l[i] = [a[i],b[i]]

ll = two_dim_merge_sort(l)

s = 0

for i in range(0,n):
    s = s + ll[i][1]
    if s >= k:
        ans = ll[i][0]
        break

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split(' '))
nums=[0]*(10**5)
for i in range(N):
  a,b=map(int,input().split(' '))
  nums[a-1]+=b
s=0
for i in range(len(nums)):
  s+=nums[i]
  if s>=K:
    print(i+1)
    break
  else:
    continue

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ans=[0]*1000001

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

for j in range(len(ans)):
    if k<=ans[j]:
        print(j)
        break
    k-=ans[j]

Submission status: Accepted

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

dic=sorted(dic.items())
for i,j in dic:
  cnt+=j
  if k<=cnt:
    print(i)
    exit()

Submission status: Accepted

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

for i in ab:
    tmp += i[1]
    if tmp >= K:
        ans = i[0]
        break
print(ans)

Submission status: Accepted

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

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