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())
d = {}
key = set([])
for _ in range(N):
  a, b = map(int, input().split())
  if a in key:
    d[str(a)] += b
  else:
    key.add(a)
    d[str(a)] = b
key = sorted(list(key))
for k in key:
  if d[str(k)] < K:
    K -= d[str(k)]
  else:
    print(k)
    break

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [0 for i in range(100001)]
for i in range(N):
  a, b = map(int, input().split())
  A[a] += b
for i in range(100001):
  if A[i] < K:
    K -= A[i]
  else:
    print(i)
    break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
S = set()
D = dict()
for _ in range(n):
    a, b = map(int, input().split())
    if a in S:
        D[a] += b
    else:
        S.add(a)
        D[a] = b
L = sorted(S)
cnt = 0
for l in L:
    cnt += D[l]
    if cnt >= k:
        print(l)
        break

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]

N,K = mint()
C = counter()
for _ in range(N):
    a,b = mint()
    C.add(a,b)
L = []
for k in C:
    L.append([k,C[k]])
L.sort(key=lambda x:x[0])
tmp = 0
for l in L:
    tmp += l[1]
    if tmp>=K:
        print(l[0])
        exit()

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    n,k = i_map()

    cnt = 0
    l = []
    for _ in range(n):
        a,b = i_map()
        l.append([a,b])

    l.sort()
    for i,j in l:
        cnt += j
        if cnt >= k:
            print(i)
            break

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# ABC 061: C – Big Array
N, K = [int(i) for i in input().split()]
a, b = [], []
for _ in range(N):
    tmp = input().split()
    a.append(int(tmp[0]))
    b.append(int(tmp[1]))

cnt = [0] * (100000 + 1)

for i in range(N):
    cnt[a[i]] += b[i]

for j in range(100000 + 1):
    if K <= cnt[j]:
        print(j)
        break
    K -= cnt[j]

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])
abc=sorted(ab,key=lambda x:x[0])
temp=0
for j in abc:
    temp+=j[1]
    if temp>=k:
        print(j[0])
        exit()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from itertools import count
N, K = map(int, input().split())
Cnt = dd(lambda:0)
for _ in range(N):
    a, b = map(int, input().split())
    Cnt[a] += b

num = 0
for i in count(1,1):
    num += Cnt[i]
    if num >= K:
        print(i)
        break

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
li = []
for i in range(n):
    temp = list(map(int, input().split()))
    li.append(temp)
#print(li)
li.sort()
#print(li)
total=0
for i in range(n):
    if i==n-1:
        #print("here")
        print(li[i][0])
        break
    total+=li[i][1]
    if total<k:
        continue
    else:
        print(li[i][0])
        break
    #print(i, total)

Submission status: Accepted

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

def main():
    n, k = map(int, input().split())
    arr = sorted([list(map(int, input().split())) for i in range(n)])
    for ab in arr:
        k -= ab[1]
        if k <= 0:
            ans = ab[0]
            break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

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

Submission status: Accepted

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

Submission status: Accepted

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

class Number:
    def __init__(self,number,times):
        self.number=number
        self.times=times

    def __eq__(self, other):
        if self.number==other.number:
            return True
        return False
    def __le__(self, other):
        if self.number<=other.number:
            return True
        return False
    def __lt__(self, other):
        if self.number<other.number:
            return True
        return False
    def __ge__(self, other):
        if self.number>=other.number:
            return True
        return False
    def __gt__(self, other):
        if self.number>other.number:
            return True
        return False

number_list=[]
for i in range(n):
    number,times=[int(i) for i in input().split()]
    number_list.append(Number(number,times))

number_list.sort()


def get(number_list,k):
    i=0
    while True:
        taishou=number_list[i]
        k=k-taishou.times
        if k<=0:
            return taishou.number
        else:
            i+=1
print(get(number_list,k))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
C = [0]*(10**5+1)
S=set()
for _ in range(N):
    a, b = list(map(int, input().split()))
    C[a] += b
    S.add(a)

L = list(S)
L.sort()
i = 0
ct = C[L[0]]
while ct < K:
    i += 1
    ct += C[L[i]]
print(L[i])

Submission status: Accepted

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

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

ans.sort()

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def is_ok(arg):
    global K
    return r[arg] >= K
def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok
N, K = map(int, input().split())
A = [0] * 10**5
for _ in range(N):
    a, b = map(int, input().split())
    A[a-1] += b
r = [A[0]]
for i in range(10**5-1):
    r.append(r[i] + A[i+1])
print(meguru_bisect(-1, 10**5)+1)

Submission status: Accepted

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

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


judge = 0
dic = {}


for i in range(n):
    if a[i] in dic:
        dic[a[i]] += b[i]
    else:
        dic[a[i]] = b[i]
#print(dic)
dic = list(dic.items())
dic.sort()
#print(dic)


for i in range(10**9):
    if judge >= k:
        print(dic[i-1][0])
        break
    else:
        judge += int(dic[i][1])
    #print(judge)

Submission status: Accepted

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

Submission status: Accepted

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

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

q = sorted(q, key=lambda x:x[0])
cnt = 0
i = 0
while cnt < k:
    a, b = q[i]
    cnt += b
    i += 1
print(a)

Submission status: Accepted

Solution code:
import heapq

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

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

heapq.heapify(q)

cnt = 0
while cnt < k:
    a, b = heapq.heappop(q)
    cnt += b
    
print(a)

Submission status: Accepted

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

cnt=0
for i in range(N):
    a,b=A[i]
    A[i][1]+=cnt
    cnt=A[i][1]

for i in range(N):
    a,b=A[i]
    if K<=b:break
print(a)

Submission status: Accepted

Solution code:
#
# abc061 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 4
1 1
2 2
3 3"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """10 500000
1 100000
1 100000
1 100000
1 100000
1 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    N, K = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(N)]

    D.sort()
    t = 0
    for d in D:
        t += d[1]
        if t >= K:
            print(d[0])
            break


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

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

for i in sorted(ar.keys()):
    k -= ar[i]
    if k <= 0:
        print(i)
        break

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)
a = sorted(a, key=lambda x: x[0])
b=0
for i in range(n):
    b+=a[i][1]
    if b>=k:
        print(a[i][0])
        exit()

Submission status: Accepted

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

def main():
    n,k = map( int , input().split() )
    A = [ 0 for i in range( 10 ** 5 + 1 ) ]
    for i in range(n):
        a,b = map( int , input().split() )
        A[ a ] += b
    
    i = 0
    sum = 0
    while( sum < k ):
        i += 1
        sum += A[i]
    print(i)



main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = []
for _ in range(n):
    A.append(list(map(int,input().split())))
A.sort(key=lambda x: x[0])
cnt = 0
while k>0:
    k-=A[cnt][1]
    cnt+=1
print(A[cnt-1][0])

Submission status: Accepted

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

l = [0] * (10**5 + 1)

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

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

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    counter = collections.Counter()
    for _ in range(N):
        a, b = il()
        counter[a] += b
    counter = sorted(counter.items(), key=lambda x: x[0])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n, k = map(int, input().split())
d = Counter([])
for i in range(n):
    a, b = map(int, input().split())
    d[a] += b
ans = 1
cnt = 0
while cnt < k:
    cnt += d[ans]
    ans += 1

print(ans - 1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc061/tasks/abc061_c
from collections import defaultdict

n, k = [int(i) for i in input().split()]
d = defaultdict(int)

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

array = sorted(d.items(), key=lambda x: x[0])
for num, count in array:
    if k > count:
        k -= count
    else:
        print(num)
        quit()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a_b = []
for _ in range(n):
    _a, _b = map(int, input().split())
    a_b.append((_a, _b))
a_b = sorted(a_b, key=lambda x: x[0])
i = 0
while k > a_b[i][1]:
    k -= a_b[i][1]
    i += 1
print(a_b[i][0])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc061/tasks/abc061_c
# K番目に小さい数

N, K = map(int, input().split())
A = [0] * (100005)
for _ in range(N):
    ai, bi = map(int, input().split())
    A[ai] += bi

for index in range(100005):
    if K <= A[index]:
        print(index)
        exit()
    else:
        K -= A[index]

Submission status: Accepted

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

Submission status: Accepted

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

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

cnt = 0
for i, c in enumerate(bucket):
    if c == 0:
        continue
    cnt += c
    if cnt >= K:
        print(i)
        exit()

Submission status: Accepted

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

cur = 0
for i in range(100100):
    cur += arr[i]
    if cur >= k:
        print(i)
        break

Submission status: Accepted

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

#print(ab)
for i in range(N):
    s += ab[i][1]
    if s >= K:
        print(ab[i][0])
        break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main2():
    N, K = map(int, input().split())
    limit = 10**5

    ins = [0 for _ in range(limit + 1)]

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

    c = 0
    for i in range(1, limit + 1):
        c += ins[i]

        if c >= K:
            print(i)
            exit()

if __name__ == "__main__":
    main2()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
l=[list(map(int,input().split()))for i in range(N)]
l.sort(key=lambda x: x[0])
ans=0
for i in l:
    if K==0:
        break
    K-=min(K,i[1])
    ans=i[0]
print(ans)

Submission status: Accepted

Solution code:
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
    
for i in range(len(ans)):
    k-=ans[i]
    if k<=0:
        print(i)
        break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# s = input()
# n = len(s) - 1
# ans = 0
# for i in range(1 << n):
#     formula = s[0]
#     for j in range(n):
#         if ((i >> j) & 1):
#             formula += '+' + s[j + 1]
#         else:
#             formula += s[j + 1]
#     ans += eval(formula)
# print(ans)
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, k = nm()
    A = [0] * (10 ** 5 + 1)
    for i in range(n):
        a, b = nm()
        A[a] += b

    sum_num = 0
    for i, a in enumerate(A):
        sum_num += a
        if sum_num >= k:
            print(i)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

d = {}
for i in range(n):
    if a[i] not in d:
        d[a[i]] = b[i]
    else:
        d[a[i]] += b[i]

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

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

Submission status: Accepted

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

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 = K - A[i][1]
    if K <= 0:
        print(A[i][0])
        exit(0)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
 
from itertools import accumulate
from bisect import bisect_left
 
N, K = map(int, input().split())
 
memo = [0] * 100010
for _ in range(N):
    a, b = map(int, input().split())
    memo[a] += b
 
print(bisect_left(list(accumulate(memo)), K))

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
import sys
sys.setrecursionlimit(10000000)
#mod = 10**9 + 7
#mod = 9982443453
mod = 998244353
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
import sys
sys.setrecursionlimit(10000000)
#mod = 10**9 + 7
#mod = 9982443453
mod = 998244353
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,k = readInts()
dic = defaultdict(int)
d = set()
for i in range(n):
    a,b = readInts()
    d.add(a)
    dic[a] += b
d = sorted(list(d))
ans = 0
for v in d:
    if ans + dic[v] >= k:
        print(v)
        exit()
    ans += dic[v]

Submission status: Accepted

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

Submission status: Accepted

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

result = {}
for _ in range(N):
    a, b = [int(x) for x in input().split()]
    if a in result:
        result[a] += b
    else:
        result[a] = b

result = sorted(result.items())

now = 0
for key, value in result:
    now += value

    if now >= K:
        print(key)
        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()
cnt = 0
for a, b in AB:
    cnt += b
    if cnt >= k:
        print(a)
        break

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
L = []
for k in range(N):
    L.append(list(map(int,input().split())))
L = sorted(L)
for e in L:
    K -= e[1]
    if K <= 0:
        print(e[0])
        exit(0)

Submission status: Accepted

Solution code:
N, K, *AB = map(int, open(0).read().split())
li = [(a, b) for a, b in zip(*[iter(AB)] * 2)]
li.sort()
for a, b in li:
    if K > b:
        K -= b
    else:
        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)])
cnt = 0
for a,b in ab:
    cnt += b
    if cnt >= k:
        print(a)
        exit()

Submission status: Accepted

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

q=[]
for _ in range(n):
    a,b=map(int,input().split())
    heapq.heappush(q,(a,b))

while k>0:
    a,b=heapq.heappop(q)
    k-=b

print(a)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    inlis = list()

    for _ in range(n):
        alis = list(map(int, input().split()))
        inlis.append(alis)
    inlis.sort()
    tmp = k
    i = 0

    while tmp > 0:
        tmp -= inlis[i][1]

        if tmp > 0:
            i += 1    
        else:
            print(inlis[i][0])
            exit()



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
c = {}
cnts = []

for i in range(n):
    a, b = list(map(int, input().split()))
    if a in c:
        cnts[c[a]][1] += b
    else:
        c[a] = len(cnts)
        cnts.append([a, b])

cnts = sorted(cnts, reverse=True)

s = 0
while True:
    si = cnts.pop()
    s += si[1]

    if s >= k:
        print(si[0])
        break

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[]
for _ in range(n):
  x,y=map(int,input().split())
  d=[x,y]
  a.append(d)
  
a.sort()
ans=0
ans1=0

for d in a:
  if (ans+d[1])>=k:
    ans1=d[0]
    break
    
  else:
    ans+=d[1]
    
print(ans1)

Submission status: Accepted

Solution code:
import itertools

n, k = list(map(int, input().split()))
ab = [[] for _ in range(n)]
for i in range(n):
    ab[i] = list(map(int, input().split()))
ab.sort(key=lambda x: x[0])
az, bz = list(zip(*ab))

accb = list(itertools.accumulate(bz))
idx = 0
for j, v in enumerate(accb):
    if k <= v:
        idx = j
        break
print(az[idx])

Submission status: Accepted

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

x=[list(map(int,input().split())) for i in range(n)]
x.sort(key=lambda x:x[0])

for i in x:
  k-=i[1]
  if k<=0:
    print(i[0])
    exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    #n = int(stdin.readline().rstrip())
    n,k = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #ab = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    a = [0]*(10**5+1)
    m = 0
    for i in range(n):
        A,B = map(int, stdin.readline().rstrip().split())
        a[A] += B
        m = max(m,A)
    j = 0
    for i in range(10**5):
        j += a[i]
        if j >= k:
            print(i)
            exit()
    print(m)



if __name__ == '__main__':
    solve()

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

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split(" ")]
 
placed = 0
elm = []
for i in range(N):
  a, b = input().split(" ")
  elm.append({
    "order": i + 1,
    "element": int(a),
    "count": int(b)
  })

elm.sort(key=lambda e: (e["element"], e["order"]))
for i in range(len(elm)):
  e = elm[i]
  placed += e["count"]
  if placed >= K:
    print(e["element"])
    break

Submission status: Accepted

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

d = {}
for _ in range(n):
  a,b = map(int, input().split())
  if a in d: d[a] += b
  else: d[a] = b
    
for x,y in sorted(d.items(), key=lambda x: x[0]):
  k -= y
  if k <= 0:
    print(x)
    exit()

Submission status: Accepted

Solution code:
def resolve():
    n, k = map(int, input().split())
    input_list = []
    for _ in range(n):
        ai, bi = map(int, input().split())
        input_list.append([ai, bi])

    input_list.sort()
    count_dic = {}
    prev_max = 0
    for key, value in input_list:
        if key in count_dic.keys():
            count_dic[key] += value
        else:
            count_dic[key] = value + prev_max
        prev_max = count_dic[key]

        if count_dic[key] >= k:
            print(key)
            return
          
resolve()