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:
import sys
input = sys.stdin.readline

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

a, b = zip(*sorted(zip(a, b)))

for i in range(N):
    K -= b[i]
    if K <= 0:
        print(a[i])
        exit()

Submission status: Accepted

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

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

a, b = zip(*sorted(zip(a, b)))

for i in range(N):
    K -= b[i]
    if K <= 0:
        print(a[i])
        exit()
    else:
        continue

Submission status: Accepted

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

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

a, b = zip(*sorted(zip(a, b)))

count = 0
while K > 0:
    K -= b[count]
    count += 1

print(a[count - 1])

Submission status: Accepted

Solution code:
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())

a, b = zip(*sorted(zip(a, b)))

count = 0
while K > 0:
    K -= b[count]
    count += 1

print(a[count - 1])

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
s=sorted(d.items(), key=lambda x:x[0])
l=0
for i,v in s:
  l+=v
  if l>=k:
    print(i)
    break

Submission status: Accepted

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
memo = [0] * (10 ** 5 + 1)
for _ in range(n):
    i, j = map(int, input().split())
    memo[i] += j
cnt = 0
for i, j in enumerate(memo):
    cnt += j
    if cnt >= k:
        print(i)
        exit()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
cnt = [0] * (10**5 + 1)
for _ in range(n):
    a, b = map(int, input().split())
    cnt[a] += b
for i in range(10**5 + 1):
    if k <= cnt[i]:
        ans = i
        break
    else:
        k -= cnt[i]
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()

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

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n, k = list(map(int, input().rstrip('\n').split()))
    ab = sorted([list(map(int, input().rstrip('\n').split())) for _ in range(n)])
    t = 0
    for a, b in ab:
        t += b
        if t >= k:
            print(a)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Accepted

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

array={}
for _ in range(n):
    a,b=map(int, input().split())
    if a not in array:
        array.setdefault(a, b)
    else:
        array[a]+=b
    
array=sorted(array.items())

count=0
for array_ele in array:
    count+=array_ele[1]
    if count>=k:
        print(array_ele[0])
        break

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
num = [0] * 100000
for i in range(n):
  a, b = map(int, input().split())
  num[a - 1] += b
for i in range(100000):
  if num[i] > 0:
    k -= num[i]
    if k <= 0:
      ans = i + 1
      break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

ab.sort()

for a, b in ab:
    k -= b
    if k <= 0:
        break

print(a)

Submission status: Accepted

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

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

ab.sort()

for a, b in ab:
    k = k - b
    if k <= 0:
        break

print(a)

Submission status: Accepted

Solution code:
from sys import stdin
N,K = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for _ in range(N):
    data.append([int(x) for x in stdin.readline().rstrip().split()])

ans = 0
for i in sorted(data):
    if K <= 0:
        break
    ans = i[0]
    K -= i[1]
    
    
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

S=[M[0][1]]
for i in range(1,N):
  S.append(S[i-1]+M[i][1])
#print(S)

ans=0
for i,s in enumerate(S):
  if s>=K:
    ans=M[i][0]
    break
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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 LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
L = []
for a, b in LIR(n):
    L += [(a, b)]


L.sort()
ret = 0
i = 0
for a, b in L:
    ret += b
    ans = a
    if ret >= k:
        break


print(ans)

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n, k = list(map(int, input().rstrip('\n').split()))
    ab = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ab.sort()
    t = 0
    mt = 0
    for a, b in ab:
        t += b
        mt = max(mt, a)
        if t >= k:
            print(mt)
            exit()


if __name__ == '__main__':
    slove()

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,key=lambda a:a[0])
tmp = 0
for i in range(N):
    if K <= tmp:
        break
    tmp += AB[i][1]
    ans = AB[i][0]
print(ans)

Submission status: Accepted

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

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

ans = 1
while K > 0:
    K -= num[ans]
    ans += 1
print(ans-1)

Submission status: Accepted

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

i=0
ans=0
while k>0:
    k=k-l[i][1]
    ans=l[i][0]
    i=i+1
print(ans)

Submission status: Accepted

Solution code:
import heapq as hq
def main():
    n,k=map(int,input().split(' '))
    a_b=[[i for i in list(map(int,input().split(' ')))] for i in range(n)]
    hq.heapify(a_b)
    cnt = 0
    while cnt < k:
        ans,c = hq.heappop(a_b)
        cnt += c
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    l, k = list(map(int, input().rstrip('\n').split()))
    ab = [list(map(int, input().rstrip('\n').split())) for _ in range(l)]
    ab.sort()
    cnt = 0
    for a, b in ab:
        cnt += b
        if cnt >= k:
            print(a)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
ab_list = [list(map(int,input().split())) for _ in range(n)]
ab_dic= {}
ab_list.sort()
for i in range(n):
  if i<n-1 and ab_list[i][0] == ab_list[i+1][0]:
    ab_list[i+1][1] += ab_list[i][1]
  else:
    ab_dic[ab_list[i][0]]=ab_list[i][1]

ab_dic = sorted(ab_dic.items(),key=lambda x:x[0])
cnt = 0
for i in range(len(ab_dic)):
  cnt += ab_dic[i][1]
  if cnt >= k:
    print(ab_dic[i][0])
    break

Submission status: Accepted

Solution code:
# C - Big Array
from operator import itemgetter
N, K = map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]
S = 0
A.sort(key=itemgetter(0))

for i in range(N):
    S += A[i][1]
    if S >= K:
        print(A[i][0])
        exit()
    else:
        pass

Submission status: Accepted

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

while K>0:
    K-=s[t][1]
    t+=1

print(s[t-1][0])

Submission status: Accepted

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

if N==1:
    a,b=map(int,input().split())
    print(a)
    exit()

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

x.sort()
sum=0
for i in range(N):
    sum+=x[i][1]
    if sum>=K:
        print(x[i][0])
        exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K,*A=map(int,open(0).read().split())
A=sorted(zip(A[::2],A[1::2]),key=lambda x:x[0])
for a,b in A:
 if K<=b:print(a);break
 K-=b

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

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

Submission status: Accepted

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

Submission status: Accepted

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

cnt = 0
for i in range(N):
	cnt += L[i][1]
	if cnt >= K:
		ans = L[i][0]
		break

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

    tmp = 0
    for i in range(N):
        a, b = ab[i]
        tmp += b
        if tmp >= K:
            print(a)
            return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,fractions
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))
def inpl_str(): return list(sys.stdin.readline().split())
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

n,k = inpl()
ab = []
for i in range(n):
    a,b = inpl()
    ab.append([a,b])
ab.sort()
cnt = 0
for i in range(n):
    if cnt + ab[i][1] >= k:
        print(ab[i][0])
        break
    else:
        cnt += ab[i][1]

Submission status: Accepted

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

while i<n:
    a=S[i][1]
    if k<=a:
        print(S[i][0])
        exit()
    else:
        k-=S[i][1]
        i+=1

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
dic = {}
for _ in range(n):
    a, b = list(map(int, input().split()))
    if a not in dic:
        dic[a] = b
    else:
        dic[a] += b
total = 0
for key, val in sorted(dic.items(), key=lambda x: x[0]):
    total += val
    if k<= total:
        print(key)
        break

Submission status: Accepted

Solution code:

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

C = [0] * (10**5 + 5)

for i in range(n):
    C[A[i][0]] += A[i][1]

for i in range(len(C)):
    if k <= C[i]:
        print(i)
        break
    else:
        k -= C[i]

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split()]
AB = [0] * N
for n in range(N):
  AB[n] = tuple([int(x) for x in input().split()])

c = 0
for a, b in sorted(AB):
  c += b
  if c >= K:
    print(a)
    break

Submission status: Accepted

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

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

ord = 0
for key in sorted(ans.keys()):
  ord += ans[key]
  if(ord >= k):
    print(key)
    exit()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
k = []
s = []
sum = 0
ans = 0
for i in range(10**5):
    k.append(0)
for i in range(N):
    s.append(list(map(int,input().split())))
for i in range(N):
    k[(s[i][0]-1)] += s[i][1]
for i in range(10**5):
    sum += k[i]
    ans += 1
    if sum >= K:
        print(ans)
        break
    else:
        continue

Submission status: Accepted

Solution code:

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

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

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

remain = K
for i in range(10**5+1):
    if ans[i] == 0:
        continue

    remain -= ans[i]
    if remain <= 0:
        print(i)
        exit()

Submission status: Accepted

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

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

AB.sort(key=lambda x: (x[0], -x[1]))

idx = 0
rignt = 0
for a, b in AB:
    idx += b
    rignt = a
    if idx >= K:
        break

print(rignt)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
ab=[[int(i) for i in input().split()]for j in range(n)]
dic={}
for a,b in ab:
    if a in dic:
        dic[a]+=b
    else:
        dic[a]=b
dic=sorted(dic.items() , key=lambda x:x[0])
check=0
for i,j in dic:
    check+=j
    if check>=k:
        print(i)
        break

Submission status: Accepted

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

s = {}

for _ in range(N):
    a, b = map(int,input().split())
    if str(a) in s.keys():s[str(a)] +=b
    else:s[str(a)]=b

s_key = list(s.keys())
s_key_int = [int(i) for i in s_key]
s_key_int.sort()

cnt = 0
num = 0

for j in s_key_int:
    cnt += s[str(j)]
    if cnt >= K:
        num=j
        break
print(j)

Submission status: Accepted

Solution code:
import bisect

N, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[0])
sumB = [0]
for a, b in AB:
    sumB.append(sumB[-1] + b)
print(AB[bisect.bisect_left(sumB, K) - 1][0])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
ab=[[0]*2 for i in range(N)]
for i in range(N):
  ab[i]=list(map(int,input().split()))
  
ab=sorted(ab,key=lambda x:x[0])
i=-1
while(K > 0):
  i+=1
  K -= ab[i][1]

print(ab[i][0])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import copy
import  math
from _bisect import *
from collections import *
from operator import itemgetter
from math import factorial
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, k = na()
li = []
for i in range(n):
    a, b = na()
    li.append((a, b))
ct = 0
for a, b in sorted(li, key=itemgetter(0)):
    ct += b
    if ct >= k:
        ans = a
        break
print(ans)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

s = set()
d = defaultdict(int)
for _ in range(n):
    a, b = map(int, input().split())
    d[a] += b
    s.add(a)

s = sorted(list(s))
# print(s)
# print(d)
s += [0]
cnt = 0
ret = None
for i in s:
    cnt += d[i]
    if cnt >= k:
        # print(i, cnt)
        ret = i
        break
print(ret)

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)
o = 0
for i in range(N):
  o += AB[i][1]
  if o >= K:
    print(AB[i][0])
    break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in range(n)])
cou=0
for r in l:
  a,b=r[0],r[1]
  cou+=b
  if cou>=k:
    print(a)
    break

Submission status: Accepted

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

acc = 0
# print(arr[:4])
for i in range(100000):
    acc += arr[i]
    # print(i,acc)
    if acc >= k:
        print(i+1)
        break

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.keys():
        c.update({a: c[a] + b})
    else:
        c[a] = b
# print(c)

cnt = 0
for i in sorted(list(c.keys())):
    cnt += c[i]
    if cnt >= k:
        print(i)
        exit()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ab = [[0, 0] for _ in range(N)]
for i in range(N):
    a, b = map(int, input().split())
    ab[i][0] = a
    ab[i][1] = b

ab = sorted(ab)

#print(ab)
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())
s=[list(map(int, input().split()))  for i in range(n)] 
x=0
s.sort()
for i in range(n):
    x+=s[i][1]
    if k<=x:
        print(s[i][0])
        exit()

Submission status: Accepted

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

ab = [[int(i) for i in input().split()] for j in range(n)]

ab.sort()

tmp = 0

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

Submission status: Accepted

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

c = 0
ans = 0
ab_list = list()

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

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

for a,b in ab_list:
    c += b
    if c >= K:
        ans = a    
        break

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc061/tasks/abc061_c
# C - Big Array

N, K = list(map(int, input().split()))
ab_list = []

for _ in range(N):
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))

ab_list = sorted(ab_list, key=lambda x: x[0])
c = 0
for a, b in ab_list:
    c += b
    if c >= K:
        ans = a
        break

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
# a_list = []
b_dict = {}

for i in range(N):
    a, b = map(int,input().split())
    if a in b_dict:
        b_dict[a] += b
    else:
        b_dict[a] = b
        
a_list = list(b_dict.keys())
a_list.sort()


for a in a_list:
    K -= b_dict[a]
    if K <= 0:
        break

print(a)

Submission status: Accepted

Solution code:
N,K = map(int, input().strip().split(' '))
l = [list(map(int, input().strip().split(' '))) for _ in range(N)]
l = sorted(l)
now = 0
for a,b in l:
  now += b
  if now >= K:
    print(a)
    exit()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
c = [0] * 100010
for _ in range(N):
    a, b = map(int, input().split())
    c[a] += b
s = 0
for i, v in enumerate(c):
    s += v
    if s >= K:
        print(i)
        exit()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=[]
for i in range(n):
    a,b=[int(j) for j in input().split()]
    l.append([a,b])
l.sort()
p=0
i=0
while True:
    if p+l[i][1]>=k:
        print(l[i][0])
        break
    else:
        p+=l[i][1]
        i+=1

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.readline
 
def main():
    n, k = map(int, input().split())
    x = sorted([list(map(int, input().split())) for _ in range(n)])
    cnt = 0
    for a, b in x:
        cnt += b
        if cnt >= k:
            print(a)
            exit()
    
main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[]
total=0
for i in range(N):
    C, B = map(int, input().split())
    A.append([C,B])

A.sort()

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

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 a, b in ab:
    cnt += b
    if cnt >= k:
        print(a)
        exit()

Submission status: Accepted

Solution code:
def main():
    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])

    i = 0
    while i < N and K > 0:
        a, b = A[i]
        K -= b
        i += 1
    return a

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

Submission status: Accepted

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

cnt = 0
idx = -1
while cnt < k:
    idx += 1
    cnt += info[idx][1]

print(info[idx][0])

Submission status: Accepted

Solution code:
# ABC061C - Big Array
import sys
input = sys.stdin.readline

from itertools import accumulate
from bisect import bisect_left as bs


def main():
    N, K = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    memo = [0] * (10 ** 5 + 1)  # memo[i] := the number of times i appears
    for a, b in A:
        memo[a] += b
    ans = bs(list(accumulate(memo)), K)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
データの特徴と定義域に注目
- 全体のデータ数は10^10で計算時間がありえない
- データ特徴としては同じ値が連続（圧縮可能）
- データを圧縮した場合のデータ数は10^5になり、空間的に許容範囲、線形探査も時間的に許容範囲
- 「空間的にも」→全要素分の配列を準備してハッシュでソート(=インデックスの場所に格納すればソートされる)
"""
(n, k) = map(int, input().split())

num = [0 for _ in range(100000 + 1)]

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

count = 0
for i, j in enumerate(num):
    if count + j >= k:
        print(i)
        break
    else:
        count += j

Submission status: Accepted

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

def main():
    N,K = map(int, input().split())
    A = {}
    for _ in range(N):
        a,b = map(int, input().split())
        if a in A:
            A[a] += b
        else:
            A[a] = b
    A = sorted(A.items(), key=lambda x:x[0])
#    print(A)
    for a,b in A:
        K -= b
        if K <= 0:
            print(a)
            break

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import bisect
import collections
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

n,k=getints()
values=getint2d(n)

k -= 1

values = list(sorted(values))
now = -1

for a,b in values:
    now_s = now + 1
    now_e = now + b
    if now_s <= k <= now_e:
        print(a)
        break
    now += b

Submission status: Accepted

Solution code:
d=dict()
n, k=map(int,input().split())
for _ in range(n):
    a,b=map(int,input().split())
    if a in d:
        d[a]+=b
    else:
        d.setdefault(a,b)
c=list(d.items())
c.sort()
cum=0

for key,v in c:
    cum+=v
    if cum>=k:
        ans=key
        break

print(ans)

Submission status: Accepted

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

if __name__ == '__main__':
    N, K = map(int, input().split())
    A, B = [], []
    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    z = zip(A, B)
    z = sorted(z)

    A, B = zip(*z)

    val = 0
    for i in range(len(A)):
        val += B[i]
        if val >= K:
            print(A[i])
            exit()

Submission status: Accepted

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

for a, b in ab_list:
  if b >= K:
    print(a)
    exit()
  else:
    K -= b

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
numbers = [list(map(int,input().split())) for _ in range(N)]
#print(numbers)
numbers.sort(key = lambda x:x[0])
#print(numbers)
cnt = 0
for idx,num in enumerate(numbers):
    cnt += num[1]
    if cnt >= K:
        print(numbers[idx][0])
        exit()

Submission status: Accepted

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

for j in range(n):
  num[int(l1[j][0])-1]+=int(l1[j][1])
#print(num)
for l in range(10**5):
  if num[l]>=k:
    print(l+1)
    break
  k-=num[l]

Submission status: Accepted

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

nums = {}
for i in range(N):
    a,b = map(int, input().split())
    nums[a] = nums.get(a, 0) + b

keys = list(nums.keys())
keys.sort()

ans = 0
for key in keys:
    if K <= nums[key]:
        ans = key
        break
    else:
        K -= nums[key]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import Counter
import heapq


class MinHeap(object):
    def __init__(self, x):
        self.heap = [e for e in x]
        heapq.heapify(self.heap)

    def push(self, value):
        heapq.heappush(self.heap, value)

    def pop(self):
        return heapq.heappop(self.heap)


def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    mh = MinHeap([])
    counter = Counter()
    for aa, bb in zip(a, b):
        if aa not in counter:
            mh.push(aa)
        counter[aa] += bb
    # print(mh.heap)
    # print(counter)

    while True:
        m = mh.pop()
        if counter[m] >= K:
            break
        else:
            K -= counter[m]
    print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)


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)])
count = 0
for i in range(n):
    count += ab[i][1]
    if count >= k:
        print(ab[i][0])
        exit()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
ans={}
for i in range(N):
    a,b=map(int,input().split())
    if a in ans:ans[a]+=b
    else :ans[a]=b
ans=sorted(ans.items(),key=lambda x:x[0])
for key,value in ans:
    K-=value
    if K<=0:break
print(key)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
N,K = map(int,input().split())
A = []
for i in range(N):
    a = list(map(int,input().split()))
    heappush(A,a)
count = 0
while count < K:
    x,y = heappop(A)
    count += y
print(x)

Submission status: Accepted

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

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

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

ab.sort()
s = 0
i = 0
while s< k:
  s += ab[i][1]
  ans = ab[i][0]
  i += 1
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
lis = []
for i in range(N):
    a, b = map(int, input().split())
    lis.append([a,b])
lis = sorted(lis)
cnt = 0
for x, y in lis:
    if cnt <= K <= cnt + y: 
        print(x)
        break
    else:
        cnt += y

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
indexes = [0]*100001
for i in range(N):
    a, b = map(int, input().split())
    indexes[a] += b
i = 0
c = 0
while K > c:
    c += indexes[i]
    i += 1
print(i-1)