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
from itertools import accumulate
from bisect import bisect_left


def main():
    n, k = map(int, input().split())
    memo = [0] * (10 ** 5 + 1)
    for _ in range(n):
        i, j = map(int, input().split())
        memo[i] += j
    ans = bisect_left(list(accumulate(memo)), k)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC061C - Big Array
import sys

input = sys.stdin.readline

from itertools import accumulate
from bisect import bisect_left


def main():
    n, k = map(int, input().split())
    memo = [0] * (10 ** 5 + 1)

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

    ans = bisect_left(list(accumulate(memo)), k)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n, k = map(int, input().split())
    memo = [0] * (10 ** 5 + 1)
    for _ in range(n):
        i, j = map(int, input().split())
        memo[i] += j
    for i, j in enumerate(memo):
        k -= j
        if k <= 0:
            print(i)
            break


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    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)
            break


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n, k = list(map(int, input().rstrip().split()))
    arr = sorted([list(map(int, input().rstrip().split())) for _ in range(n)])
    cur, cnt = 0, 0
    for i, j in arr:
        cnt += j
        if cnt >= k:
            print(i)
            break


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n, k = list(map(int, input().rstrip().split()))
    memo = [0] * (10 ** 5 + 1)
    for _ in range(n):
        i, j = map(int, input().rstrip().split())
        memo[i] += j
    cnt = 0
    for i, j in enumerate(memo):
        cnt += j
        if cnt >= k:
            print(i)
            break


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n, k = list(map(int, input().rstrip().split()))
    arr = [list(map(int, input().rstrip().split())) for _ in range(n)]
    memo = [0] * (10 ** 5 + 1)
    for i, j in arr:
        memo[i] += j
    cnt = 0
    for i, j in enumerate(memo):
        cnt += j
        if cnt >= k:
            print(i)
            break


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

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

N, K = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

AB.sort()
A, B = list(zip(*AB))

print(A[np.searchsorted(np.array(B).cumsum(), K)])

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np
import bisect

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

N, K = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

AB.sort()
A, B = list(zip(*AB))
B = np.array(B).cumsum()

print(A[bisect.bisect_left(B, K)])

Submission status: Accepted

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

def main():
    n, k = list(map(int, input().rstrip().split()))
    arr = sorted([list(map(int, input().rstrip().split())) for _ in range(n)])
    cur, cnt, ans = 0, 0, 0
    for i, j in arr:
        ans = i
        cnt += j
        if cnt >= k:
            break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n, k = list(map(int, input().rstrip().split()))
    arr = sorted([list(map(int, input().rstrip().split())) for _ in range(n)])
    cur, cnt, ans = 0, 0, 0
    while cnt < k:
        cnt += arr[cur][1]
        ans = arr[cur][0]
        cur += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 配列じゃなくて辞書なり連想配列なりハッシュなりを使いましょう おしまい
n, k = map(int, input().split())
h = {}
for _ in range(n):
    a, b = map(int, input().split())
    if a in h:
        h[a] += b
    else:
        h[a] = b

arr = [x for x in h.items()]
arr = list(sorted(arr, key=lambda x: x[0]))
count = 0

for a in arr:
    if count + a[1] >= k:
        print(a[0])
        exit()
    else:
        count += a[1]

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
a_max = 100000
t = [0 for _ in range(a_max)]

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

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

print(ans)

Submission status: Accepted

Solution code:
amax = 100000
cnt = [0 for i in range(amax+1)]


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

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


for ans in range(1, amax+1):
    if K <= cnt[ans]:
        print(ans)
        break
    K -= cnt[ans]

Submission status: Accepted

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

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

lst.sort()


for i in range(N):
    if K <= lst[i][1]:
        print (lst[i][0])
        exit()
    else:
        K -= lst[i][1]

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
buckets = [0]*(10**5)

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

cnt = 0
for i in sorted(D.keys()):
    cnt += D[i]
    if cnt >= K:
        print(i)
        exit()

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

tmp = 0
for i in sorted(D.keys()):
    tmp += D[i]
    if tmp >= K :
        print(i)
        break

Submission status: Accepted

Solution code:
manipulation_times, num = tuple(int(i) for i in input().split(" "))
num_list = []
for i in range(manipulation_times):
    num_list.append(tuple(int(i) for i in input().split(" ")))


def num_0(tup):
    return tup[0]


num_list.sort(key=num_0)
count = 0
for i in num_list:
    count += i[1]
    if count >= num:
        print(i[0])
        break

Submission status: Accepted

Solution code:
import heapq
n,k = map(int,input().split())
d = {}
z = []
for i in range(n):
    a,b = map(int,input().split())
    z.append([a,b])
    d[a] = 0
for i in range(len(z)):
    d[z[i][0]]+=z[i][1]
c = sorted(d.keys())
l=0
for i in range(len(c)):
    if(k<=0):
        print(c[i-1])
        l+=1
        break
    k-=d[c[i]]
if(l!=1):
    print(c[-1])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
lis_tup = []
for _ in range(n):
  lis_tup.append(tuple(map(int,input().split())))
lis_tup.sort(key=lambda tup: tup[0])
i = 0
while(k>0):
  k -= lis_tup[i][1]
  i += 1
print(lis_tup[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)])
c=0
for a,b in l:
    c+=b
    if c>=k:
        print(a)
        exit(0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,k = list(map(int,input().split()))
bucket = [0]*(10**5+1)

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

ret = 0
cum = 0
while cum < k:
    ret+=1
    cum+=bucket[ret]
print(ret)

Submission status: Accepted

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

n, k = map(int, input().split())
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
ab = sorted(ab, key=lambda x:x[0])
cnt = 0
for a, b in ab:
    cnt += b
    if k <= cnt:
        ans = a
        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(key=lambda x: x[0])

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())
ab = [tuple(map(int, input().split())) for _ in range(N)]

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

cnt = 0
i = 0
while True:
    a, b = ab[i]
    cnt += b
    if cnt >= K:
        print(a)
        exit()
    i += 1

Submission status: Accepted

Solution code:
nk = input().split(" ");
n = int(nk[0]);
k = int(nk[1]);
ab = [[0] * 2 for i in range(n)]
for i in range(n) :
	ab_i = input().split(" ");
	ab[i][0] = int(ab_i[0]);
	ab[i][1] = int(ab_i[1]);
ab.sort(key=lambda x:x[0] );
j = 0;
l = 0;
while l + ab[j][1] < k :
	l = l + ab[j][1];
	j = j + 1;
print(ab[j][0]);

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append((a, b))
A = sorted(A)
t = 0
i = 0
while t < K:
    t += A[i][1]
    i += 1
print(A[i-1][0])

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
nums = []
for _ in range(n):
    a, b = map(int, input().split())
    nums.append((a,b))
nums.sort(key=lambda x: x[0])
for t in nums:
    k -= t[1]
    if k <= 0:
        print(t[0])
        break

Submission status: Accepted

Solution code:

def list_pos(cnt,a,b,ans):
    if ans  >= b :
        return cnt-1
    else :

        ans += a[cnt][1]
        cnt += 1
        return list_pos(cnt,a,b,ans)
import sys
sys.setrecursionlimit(100000)
N,K = map(int,input().split())
para = {}
for i in range(N):
    a,b  = map(int,input().split())
    if not a in para.keys():
        para[a] = b
    else : para[a] += b

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

p = list_pos(0,para,K,0)
print("{}".format(para[p][0]))

Submission status: Accepted

Solution code:
import numpy as np
import bisect

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

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

pre_num = 0
lst = []
for i in range(N):
  if AB[i][0] == pre_num:
    lst[-1][1] += AB[i][1]
  else:
    pre_num = AB[i][0]
    lst.append(AB[i])
    
AB_cumsum = np.array(lst)[:,1].cumsum()
idx = bisect.bisect_left(AB_cumsum, K)
ans = lst[idx][0]
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
N , K=  list(map(int,input().split(" ")))
ar = []
for _ in range(N):
    a,b = list(map(int,input().split(" ")))
    ar.append((a,b))
ar.sort(key=lambda x:x[0])
co = 0
for num in ar:
    co += num[1]
    if co >= K:
        print(num[0])
        exit()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
putting = []
for i in range(0, N):
	putting.append(list(map(int, input().split())))
putting.sort(key = lambda v: v[0])
sum = 0
for i in range(0, N):
	sum += putting[i][1]
	if K <= sum:
		print(putting[i][0])
		break

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc061/tasks/abc061_c

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    N, K = map(int, input().split())
    ab = []
    for _ in range(N):
        a, b = map(int, input().split())
        ab.append((a, b))
    ab.sort(key=lambda x: x[0])

    rest = K
    for a, b in ab:
        if rest <= b:
            print(a)
            exit()
        else:
            rest -= b


if __name__ == '__main__':
    main()

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(key = lambda x:x[0])

sum_b = 0
i = 0

while True:
    sum_b += A[i][1]
    if sum_b >= K:
        print(A[i][0])
        exit()
    else:
        i += 1

Submission status: Accepted

Solution code:
import math

l = input().split()
N = int(l[0])
K = int(l[1])

AB = []

for i in range(N):
    l = input().split()
    a = int(l[0])
    b = int(l[1])
    AB.append((a, b))

AB.sort(key=lambda x: x[0])
#print(N, K, AB)

sum = 0
ans = 0
for ab in AB:
    sum += ab[1]
    if sum >= K:
        ans = ab[0]
        break

print(ans)

Submission status: Accepted

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

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

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

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 in d.keys():
        d[a]+=b
    else:
        d[a]=b
keys=sorted(d.keys())
for x in keys:
    k-=d[x]
    if k<=0:
        print(x)
        break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
ab = [0]*N
for i in range(N):
    ab[i] = tuple(map(int,input().split()))
ab.sort(key= lambda x:x[0])
m = 10**5
for a,b in ab:
    K -= b
    m = a
    if K <= 0:
        print(m)
        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
K = sorted(D.keys())
i = 0
while k > 0:
    k -= D[K[i]]
    i += 1
print(K[i - 1])

Submission status: Accepted

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

count = 0
for i in sorted(ab):
    count += i[1]
    if count >= k:
        print(i[0])
        exit()

Submission status: Accepted

Solution code:
from operator import itemgetter
n,k = (int(i) for i in input().split())
c = 0
e = sorted([tuple([int(i) for i in input().split()]) for i in range(n)],key=itemgetter(0))
for a,b in e:
    if c<=k<=c+b:
        print(a)
        exit()
    c+=b

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

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

  l=[]
  for _ in range(n):
    l.append(LI())

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

  sm=0
  for i in range(n):
    sm+=l[i][1]

    if sm>=k:
      return l[i][0]

print(main())

Submission status: Accepted

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

import numpy as np

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

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

A = np.array(A,dtype=np.int64)
A = A.cumsum()
answer = (A >= K).nonzero()[0].min()
print(answer)

Submission status: Accepted

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

from collections import defaultdict
DICT=defaultdict(int)

for a,b in AB:
    DICT[a]+=b

for k in sorted(DICT):
    if DICT[k]>=K:
        print(k)
        break
    else:
        K-=DICT[k]

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
a.sort()
now = 0
for i in a:
  now += i[1]
  if now >= 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()
i=0
for a,b in ab:
    if i<K<=i+b:
        print(a)
        quit()
    i+=b

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k =  [ int(v) for v in input().split() ]
num_list = sorted([ tuple(map(int, input().split())) for i in range(n) ])
order_list, value_list = [ 0 for i in range(n) ], [ 0 for i in range(n) ]
for i in range(n):
	order_list[i] = num_list[i][1] + order_list[i-1]
	value_list[i] = num_list[i][0]


for i in range(n):
	if order_list[i] - k >= 0:
		print(value_list[i])
		break

Submission status: Accepted

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

Submission status: Accepted

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

for A, B in sorted(AB):
  K -= B
  if K <= 0:
    print(A)
    break

Submission status: Accepted

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

count = 0
for key, value in sorted(num_dict.items()):
    count += value
    if count >= k:
        print(key)
        break

Submission status: Accepted

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

""" 方針
[入力例１]
3 4
1 1
2 2
3 3

ans = [1, 2, 2, 3, 3, 3]
K=4より、答えは3


"""

def solve():
    N, K = list(map(int, input().split()))
    A, B = [], []

    num_cnt_hash = {}
    for i in range(N):
        a, b = list(map(int, input().split()))

        if not a in num_cnt_hash:
            num_cnt_hash[a] = 0
        num_cnt_hash[a] += b
    
    nums = list(num_cnt_hash.keys())
    nums.sort()

    k = 0
    for num in nums:
        k += num_cnt_hash[num]
        if k >= K:
            print(num)
            return


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from sys import exit, stdin
N, K = [int(_) for _ in stdin.readline().rstrip().split()]
AB = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]
AB.sort(key=lambda ab:ab[0])
total_index = 0
for ab in AB:
    total_index += ab[1]
    if total_index >= K:
        print(ab[0])
        exit()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [0 for x in range(n)]
b = [0 for x in range(n)]
for i in range(n):
    a[i],b[i] = map(int,input().split())
cnt = [0 for x in range(10**5+1)]
for i in range(n):
    cnt[a[i]] += b[i]
    # print(f'{a[i]}, {b[i]}, {cnt[a[i]]}')
i = 1
sum = 0
while sum < k:
    sum += cnt[i]
    if sum >= k: break
    i += 1
    # print('@', i, ' ', sum)
print(i)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math
from collections import defaultdict


def main():
  N,K = map(int, input().split())
  ABn = defaultdict(lambda:0)
  for _ in range(N):
    a,b = map(int, input().split())
    ABn[a] += b

  for i in sorted(ABn.keys()):
    ret = i
    K -= ABn[i]
    if K <= 0:
      return ret


if __name__ == "__main__":
  ret = main()
  print(ret)

Submission status: Accepted

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

Submission status: Accepted

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

cand = {}
sums = 0
ans = 0
for i in ab:
    if(i[0] in cand):
        cand[i[0]] += i[1]
    else:
        cand[i[0]] = i[1]

cand = sorted(cand.items(), key=lambda x:x[0])
for i in cand:
    sums+=i[1]
    if(sums>=K):
        ans = i[0]
        break
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

k = 0
for _ in range(N):
    a, b = heapq.heappop(heap)
    if k + b < K:
        k += b
    else:
        print(a)
        break

Submission status: Accepted

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

ab.sort(key = lambda x:x[0])
idx = 0
i = 0
while True:
    if idx + ab[i][1] > K-1:
        ans = ab[i][0]
        break
    else:
        idx += ab[i][1]
    i += 1
    


print(ans)

Submission status: Accepted

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

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

test = {}

for i in arr:
    if i[0] in test:
        test[i[0]] += i[1]
    else:
        test[i[0]] = i[1]

test = sorted(test.items())

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

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()
for i in range(N):
        K-=L[i][1]
        if K>=1:
                continue
        else:
                print(L[i][0])
                exit()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# vim: set fileencoding=utf-8:
import sys
input = sys.stdin.readline

N, K = [int(ele) for ele in input().split()]
ab = [0]*N
for i in range(N):
    ab[i] = [int(ele) for ele in input().split()]


def main():
    ab.sort()  # pythonのsortは１つ目の要素に関する安定ソート
    ans = 0
    k = 0
    for ele in ab:
        k += ele[1]
        if k < K:
            continue
        elif K <= k:
            ans = ele[0]
            break

    print(ans)


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


class Node():

    def __init__(self):
        self.idx = None
        self.left = None
        self.right = None
        self.parent = None
        return

    def pre_order(self):
        global pre_order_str
        pre_order_str += str(self.idx) + " "
        if self.left:
            self.left.pre_order()

        if self.right:
            self.right.pre_order()

    def in_order(self):
        global in_order_str

        if self.left:
            self.left.in_order()

        in_order_str += str(self.idx) + " "

        if self.right:
            self.right.in_order()

    def post_order(self):
        global post_order_str
        if self.left:
            self.left.post_order()

        if self.right:
            self.right.post_order()

        post_order_str += str(self.idx) + " "


class HeapHelper():
    """HeapContrler.
    完全二分木を二分ヒープで表現した配列 A に対して、
    HeapHelper.parent(idx) とするとそのノードの親の添字を返す
    存在しない場合は Falseを返す

    Returns:
        [type] -- [description]
    """

    def __init__(self):
        return

    @staticmethod
    def parent(i):
        if i == 1:
            return False

        return int(i/2)

    @staticmethod
    def left(i):
        l_idx = 2*i
        if H < l_idx:
            return False

        return l_idx

    @staticmethod
    def right(i):
        r_idx = 2*i + 1
        if H < r_idx:
            return False

        return r_idx


if __name__ == "__main__":
    main()

Submission status: Accepted

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

A = [0] * 10**5

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

c = 0

for i in range(10**5):
    c += A[i]
    if c >= K:
        break

print(i+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,K = map(int,input().split())
d = defaultdict(int)
for i in range(N):
    a,b = map(int,input().split())
    d[a] += b
ls = [(k,d[k]) for k in d.keys()]
ls.sort(key = lambda x:x[0])
cnt = 0
for i in range(len(ls)):
    cnt += ls[i][1]
    if cnt >= K:
        print(ls[i][0])
        break

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in [0]*N])
for a,b in ab:
    K -= b
    if K <= 0:
        print(a)
        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()

s = [0] * (N+1)

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

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

# anss = [0 for i in range(K)]
inserts = [[] for i in range(N)]
for i in range(N):
    inserts[i] = [int(i) for i in input().split()]


inserts.sort()
cnt = 0
for insert in inserts:
    cnt += insert[1]
    ans = insert[0]
    # print(cnt)
    if cnt >= K:
        break

print(ans)

Submission status: Accepted

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

ans = -1  
now = 0
for k, v in sorted(dic.items()):
  now += v
  if now >= K:
    ans = k
    break
print(ans)

Submission status: Accepted

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


for i in range(N):
    ai, bi = map(int, input().split())
    lst[ai] += bi

for ai, bi in enumerate(lst):
    length += bi
    if length >= K:
        ans = ai
        print(ans)
        break

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
lst_ab = sorted([tuple(map(int, input().split())) for _ in range(N)])
length = 0


for i in range(N):
    ai, bi = lst_ab[i][0], lst_ab[i][1]
    length += bi
    if length >= K:
        ans = ai
        print(ans)
        break

Submission status: Accepted

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

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

t = 0
for i in range(100005):
    t += D[i]
    if t >= K:
        print(i)
        exit()

Submission status: Accepted

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

l = {}
for a, b in AB:
	if a not in l:
		l[a] = b
	else:
		l[a] += b

k = K
for m in sorted(l):
	k -= l[m]
	if k <= 0:
		print(m)
		break

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

from itertools import accumulate
from bisect import bisect_left

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

memo = [0] * 100010
for _ in range(N):
    a, b = [int(i) for i in input().split()]
    memo[a] += b

print(bisect_left(list(accumulate(memo)), K))

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_left

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

memo = [0] * 100010
for _ in range(N):
    a, b = [int(i) for i in input().split()]
    memo[a] += b

print(bisect_left(list(accumulate(memo)), K))

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_left

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

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

print(bisect_left(list(accumulate(memo)), K))

Submission status: Accepted

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

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

for i, b in enumerate(memo):
    if K <= memo[i]:
        print(i)
        quit()
    K -= memo[i]

Submission status: Accepted

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

L.sort()
k = 0
for a, b in L:
    if k + b >= K:
        print(a)
        quit()
    k += b