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

Submission status: Accepted

Solution code:
from collections import Counter
N, K = map(int, input().split())
C = Counter()
for _ in range(N):
    a, b = map(int, input().split())
    C[a] += b
cnt = 0
for x in sorted(C):
    cnt += C[x]
    if cnt >= K:
        print(x)
        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
D = sorted(D.items(),key=lambda x:x[0])
for i in D :
    K -= i[1]
    if K <= 0 :
        ans = i[0]
        break
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
L = [[int(i) for i in input().split()] for j in range(N)]
L.sort(key=lambda x:x[0])
t = 0
for i in L:
    if t < K - i[1]:
        t += i[1]
    else:
        print(i[0])
        break

Submission status: Accepted

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

for i in range(n):
    ans = t[i][0]
    k -= t[i][1]
    if k <= 0:
        break

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()
array_num = 0
for x, y in ab:
    array_num += y
    if array_num >= K:
        print(x)
        break

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
cnt = [0]*(int(1e5)+1) # 1-indexed
for _ in range(N):
    a,b = map(int, input().split())
    cnt[a] += b

s = 0
for i,c in enumerate(cnt):
    s += c
    if s>=K:
        print(i)
        break

Submission status: Accepted

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

count = 0
for i, a in enumerate(array, 1):
    count += a
    if count >= K:
        print(i)
        break

Submission status: Accepted

Solution code:
N, K = [int(_) for _ in input().split()]
numbers = {}
for _ in range(N):
    a, b = [int(_) for _ in input().split()]
    numbers[a] = numbers.get(a, 0) + b
count = 0
for key, value in sorted(numbers.items()):
    count += value
    if count >= K:
        print(key)
        exit()

Submission status: Accepted

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

D = {}
count = 0
for i in range(N):
    a, b = (int(i) for i in input().split())
    if a in D:
        D[a] += b
    else:
        D[a] = b

else:
    aL = [a for a in D.keys()]
    aL.sort()
    for a in aL:
        count += D[a]
        if count >= K:
            print(a)
            break

Submission status: Accepted

Solution code:
N, K = map(int, raw_input().split())
a = [0]*N
b = [0]*N
for i in range(N):
  a[i], b[i] = map(int, raw_input().split())
sa = range(N)
sa.sort(key=lambda i:a[i])
c = 0
for i in range(N):
  c += b[sa[i]]
  if c >= K:
    print a[sa[i]]
    break

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,k = map(int, input().split())
ab = []
for _ in range(n):
    a,b = map(int, input().split())
    ab.append((a,b))

ab.sort()

res = 0
for a,b in ab:
    if b>=k:
        res = a
        break
    else:
        k -= b
print(res)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])
s.sort()
t = 0
for i in range(n):
    if i == 0:
        if k <= s[i][1]:
            print(s[i][0])
            break
    elif i == n - 1:
        print(s[i][0])
        break
    else:
        t += s[i - 1][1]
        if t < k <= t + s[i][1]:
            print(s[i][0])
            break

Submission status: Accepted

Solution code:
def main():
    l = []
    N, K = map(int, input().split())
    d_num = {i: 0 for i in range(100002)}
    for i in range(N):
        a, b = map(int, input().split())
        d_num[a] = d_num[a] + b

    for i in range(100002):
        K = K - d_num[i+1]

        if K <= 0:
            break

    print(i+1)

main()

Submission status: Accepted

Solution code:
import numpy as np

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

a_order = np.argsort(a_list)
kc = 0
for i in range(N):
    kc += b_list[a_order[i]]
    if kc >= K:
        print(a_list[a_order[i]])
        break

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
a = [[0,0] for i in range(n)]
for i in range(n):
    a[i][0], a[i][1] = [int(i) for i in input().split()]
a = sorted(a)
sum = 0
for i in range(n):
    sum += a[i][1]
    if sum >= k:
        print(a[i][0])
        exit()

Submission status: Accepted

Solution code:
arr = []
n,k = map(int,raw_input().split())
for i in range(n):
    a,b = map(int,raw_input().split())
    arr.append((a,b))
arr.sort()
aa = 0
for a,b in arr:
    aa += b
    if aa >= k:
        print a
        exit()

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
array=[]
for i in range(n):
    array.append(list(map(int,input().split())))
array.sort(key=lambda x:x[0])
q=True
count=0
i=0
while q:
    count +=array[i][1]
    if k<=count:
        print(array[i][0])
        exit()
    else:
        i +=1

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
emp_file = {}
num_list = []
count = 0
for i in range(n):
    a, b = map(int, input().split())
    num_list.append([a, b])
for i in range(n):
    emp_file[num_list[i][0]] = 0
for i in num_list:
    emp_file[i[0]] += i[1]
sort_file = sorted(emp_file.items())

sum_ = 0

for i in range(len(sort_file)):
    if sum_ < k:
        sum_ += sort_file[i][1]
        if sum_ >= k:
            print(sort_file[i][0])

Submission status: Accepted

Solution code:
N, K= map(int, input().split())
g =[[] for i in range(N)]
h=0
for i in range(N):
    a, b = map(int, input().split())
    g[i].append(a)
    g[i].append(b)
def S(L):
    return L[0]
def T(L):
    return L[1]
g.sort(key=S)
for j in range(N):
    h+=T(g[j])
    if h>=K:
        y=S(g[j])
        break
print(y)

Submission status: Accepted

Solution code:
class Num:
    def __init__(self, a, b):
        self.a = a
        self.b = b


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

m = {}
num_list = []
for num in nums:
    if num.a not in m:
        num_list.append(num.a)
    m.setdefault(num.a, 0)
    m[num.a] += num.b

num_list.sort()
cnt = 0
for n in num_list:
    cnt += m[n]
    if K <= cnt:
        print(n)
        break

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
num_list = []
for _ in range(n):
    num_list .append(list(map(int,input().split())))
num_list.sort()
cnt = 0
ans = 0

for num in num_list:
    if cnt < k:
        cnt += num[1]
        ans  = num[0]
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
List_First=[[int(i) for i in input().split()] for i in range(N)]
List_a=[i[0] for i in List_First]
List_b=[i[1] for i in List_First]
List_n=[i for i in range(N)]
new_List_n=sorted(List_n,key=lambda x:List_a[x])
new_List_a=[List_a[i] for i in new_List_n]
new_List_b=[List_b[i] for i in new_List_n]
S=0
m=-1
while S<K:
  m+=1
  S+=new_List_b[m]
print(new_List_a[m])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
s=[]
tmp_a=[]
tmp=0
for i in range(n):
    a,b=map(int,input().split())
    tmp_a.append(a)
    s.append([a,b])#aをb個挿入する
s.sort()
tmp1_a=set(tmp_a)
sS=[]
s_sum=s[0][1]
for i in range(1,n):
    if s[i-1][0]==s[i][0]:
        s_sum+=s[i][1]
    else:
        sS.append([s[i-1][0],s_sum])
        s_sum=0
        s_sum+=s[i][1]
    if i==(n-1):
        sS.append([s[i][0],s_sum])
for i in range(len(tmp1_a)):
    tmp+=sS[i][1]
    if tmp>=k:
        print(sS[i][0])
        break

Submission status: Accepted

Solution code:
# encoding: utf-8
N, K = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[0])

length = 0
for ai, bi in ab:
    if length + bi >= K: break
    length += bi

print(ai)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

a = []
b = []

for i in range(N):
	a_i, b_i = map(int, input().split( ))
	a.append(a_i)
	b.append(b_i)

d = defaultdict(int)

for i in range(N):
    if a[i] in d:
        d[a[i]] += b[i]
    else:
        d[a[i]] = b[i]

d_sorted = sorted(d.items())

l = 0

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

Submission status: Accepted

Solution code:
import sys
(n, k) = list(map(int, input().split()))
mapa = {}
for _ in range(n):
    (a, b) = list(map(int, input().split()))
    if a in mapa:
        mapa[a] += b
    else:
        mapa[a] = b

mapa = sorted(mapa.items())
for i in mapa:
    if k <= i[1]:
        print(i[0])
        sys.exit(0)
    else:
        k -= i[1]

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.sort()
i=0
while K>0:
    K=K-lis[i][1]
    i+=1


print(lis[i-1][0])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
ab = {}
for _ in range(N):
    a,b = map(int, input().split())
    if a in ab:
        ab[a] += b
    else:
        ab[a] = b

# print(ab)
sum = 0
key = 0
for k,v in sorted(ab.items(), key=lambda x: x[0]):  # key
    sum += v
    if sum >= K:
        key = k
        break

print(key)

Submission status: Accepted

Solution code:
import sys
def 解():
    iN,iK = [int(_) for _ in input().split()]
    #aData = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    d = {}
    for a,b in [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]:
        if a in d:
            d[a] += b
        else:
            d[a] = b
    iC = 0
    for a in sorted(d.keys()):
        iC += d[a]
        if iK <= iC :
            print(a)
            exit()
解()

Submission status: Accepted

Solution code:
import sys
iN,iK = [int(_) for _ in input().split()]
#aData = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

d = {}
for _ in range(iN):
    a,b = [int(_) for _ in sys.stdin.readline().split()]
    if a in d:
        d[a] += b
    else:
        d[a] = b
iC = 0
for a in sorted(d.keys()):
    iC += d[a]
    if iK <= iC :
        print(a)
        exit()

Submission status: Accepted

Solution code:
import sys
iN,iK = [int(_) for _ in input().split()]
#aData = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

d = {}
for a,b in [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]:
    if a in d:
        d[a] += b
    else:
        d[a] = b
iC = 0
for a in sorted(d.keys()):
    iC += d[a]
    if iK <= iC :
        print(a)
        exit()

Submission status: Accepted

Solution code:
import sys
iN,iK = [int(_) for _ in input().split()]
aData = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

d = {}
for a,b in aData:
    if a in d:
        d[a] += b
    else:
        d[a] = b
iC = 0
for a in sorted(d.keys()):
    iC += d[a]
    if iK <= iC :
        print(a)
        exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = []
b = []
hairetu = []
for i in range(N):
    A, B = map(int, input().split())
    hairetu.append([A, B])

hairetu.sort()
for i in range(N):
    K -= hairetu[i][1]
    if K <= 0:
        print(hairetu[i][0])
        break

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = []
for i in range(n):
    m,o = map(int,input().split())
    a.append([m,o])
a.sort()
ans = 0
remain = k
for j in a:
    remain -= j[1]
    if remain <= 0:
        ans = j[0]
        break
print(ans)

Submission status: Accepted

Solution code:
def solve(N, K, ABs):
    counts = {i: 0 for i in range(1, 10 ** 5 + 1)}
    for a, b in ABs:
        counts[a] += b
    s = 0
    for c, count in counts.items():
        s += count
        if K <= s:
            return c


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    ABs = []
    for _ in range(N):
        ABs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, ABs))

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]


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

Submission status: Accepted

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

for i in range(N):
  cc = list(map(int, input().split()))
  num.append(cc)
  
num = sorted(num , key = lambda x : x[0])
  
for i in num:
  K -= i[1]
  if K <= 0:
    print(i[0])
    break

Submission status: Accepted

Solution code:
n, k = map(int , input().split())
a = []
b = []
cnt = 0
for i in range(n):
    atem, btem = map(int , input().split())
    a.append(atem)
    b.append(btem)
c = list(zip(a, b))
c.sort()
a, b = zip(*c)
for i in range(n):
    cnt += b[i]
    if cnt >= k:
        print(a[i])
        break

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
l = []
for _ in [0]*n:
  l += [list(map(int, input().split()))]
l.sort()
s = 0
i = -1
while s<k:
  i += 1
  s += l[i][1]
print(l[i][0])

Submission status: Accepted

Solution code:
def bakt():
    len_s = [0]*int(1e+5+1)
    N, K = map(int, input().split())
    for _ in range(N):
        a, b = map(int, input().split())
        len_s[a] += b
    len_a = 0
    for i, j in enumerate(len_s):
        len_a += j 
        if len_a >= K:
            print(i)
            break
            
            
if __name__ == '__main__':
    bakt()

Submission status: Accepted

Solution code:
def bakt():
    len_s = [0 for _ in range(int(1e+5+1))]
    ans = 0
    N, K = map(int, input().split())
    for _ in range(N):
        a, b = map(int, input().split())
        len_s[a] += b
    len_a = 0

    for i, j in enumerate(len_s):
        len_a += j 
        if len_a >= K and ans == 0:
            ans = i
    print(ans)
if __name__ == '__main__':
    bakt()

Submission status: Accepted

Solution code:
def main():
    len_s = 0
    ans = -1
    dic = {}
    N, K = map(int, input().split())
    for _ in range(N):
        a, b = map(int, input().split())
        if a not in dic:
            dic[a] = b
        else:
            dic[a] += b
    dic = sorted(dic.items())
    for key, value in dic:
        len_s += value
        if len_s >= K and ans == -1:
            ans = key
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


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

n,k = getNM()
nums = []
for i in range(n):
    a,b = getNM()
    nums.append((a,b))

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

for n in nums:
    a,b = n
    k-=b
    if k <= 0:
        print(a)
        break

Submission status: Accepted

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

Submission status: Accepted

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

AB = sorted(AB)

cnt = 0
ans = 0
for a,b in AB:
    cnt += b

    if cnt >= K:
        ans = a
        break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

current = 0
for q in sorted(Q.items()):
    if current + q[1] < K:
        current += q[1]
    else:
        print(q[0])
        break

Submission status: Accepted

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

Submission status: Accepted

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

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

count = 0

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

Submission status: Accepted

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

index=0
numberL=[]
while index < n:
    a, b = map(int, input().split())
    numberL.append([a, b])
    index+=1

numberL.sort()

index2=0
sum=0
while index2 < len(numberL):
    sum+=numberL[index2][1]
    if sum < k:
        index2+=1
    else:
        print(numberL[index2][0])
        break

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:


import numpy as np

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

a_list = []
b_list = []
for i in range(N):
    a,b = map(int,raw_input().split())
    a_list.append(a)
    b_list.append(b)
    
a_list=np.array(a_list)

arg = a_list.argsort()

count=0
for i in range(N):
    count+=b_list[arg[i]]
    if count>=K:
        print a_list[arg[i]]
        break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
il = lambda: list(map(int, input().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]

n, k = il()
l = sorted(ils(n, "il()")) + [[10 ** 5+10, 10 ** 5+10]]
cnt = 1
for i, (a, b) in enumerate(l):
    if cnt > k:
        print(l[i-1][0])
        break
    else:
        cnt += b

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    N, K = li_input()
    L = []
    D = collections.defaultdict(lambda: 0)

    for i in range(N):
        a, b = li_input()
        L.append(a)
        D[a] += b

    L = sorted(set(L))

    c = 0
    for l in L:
        c += D[l]

        if c >= K:
            print(l)
            return

main()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


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

    total = 0
    for k, v in sorted(d.items()):
        total += v
        if K <= total:
            print(k)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

cnt = 0
for ai in a:
    cnt += ai[1]
    if cnt >= k:
        print(ai[0])
        break

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


from collections import Counter

cnt = Counter([])

n,k = li()

num = []
index = []

for _ in range(n):
    a,b = li()
    cnt[a] += b


res = k
for key in sorted(cnt.keys()):
    if res - cnt[key] <= 0:
        print (key)
        break
    
    res -= cnt[key]

Submission status: Accepted

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

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

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

Submission status: Accepted

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

ret = {}

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

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

Submission status: Accepted

Solution code:
from collections import Counter
N,K = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]

ctr = Counter()
for a,b in src:
    ctr[a] += b

now = 0
for k,v in sorted(ctr.items()):
    if now + v < K:
        now += v
    else:
        print(k)
        break

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
d = []
for _ in range(n):
    d.append(list(map(int,input().split())))
d.sort(key=lambda x: x[0])
count = 0
for x,y in d:
    count += y
    if count >= k:
        break
print(x)

Submission status: Accepted

Solution code:
f = lambda: list(map(int,input().split()))
f_ = lambda: [int(x)-1 for x in input().split()]

n,k = f()
d = []
for _ in range(n):
    a,b = f()
    d.append((a,b))
d.sort(key=lambda x: x[0])
count = 0
for x,y in d:
    count += y
    if count >= k:
        break
print(x)

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

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

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

ls.sort()

for a, b in ls:
    K -= b
    if K <= 0:
        print a
        exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
dic = {}

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

dic = {}

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


ans = sorted(dic.items())

for i,j in ans:
    K -= j
    if K <= 0:
        print(i)
        break

Submission status: Accepted

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

    d = {}
    key_list = set()

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

        key_list.add(a)

    key_list = sorted(key_list)

    curr_num = 0
    for key in key_list:
        curr_num += d[key]
        if curr_num >= k:
            print(key)
            return


if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
# cook your dish here
n,k = map(int,input().split())
c = 0
j = []
for i in range(n):
    a,b = map(int,input().split())
    j.append([a,b])
j.sort()
for i in range(n):
    d = c
    c += j[i][1]
    if d +1 <= k and k <= c:
        print(j[i][0])

Submission status: Accepted

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

A = []

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

A.sort()

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

Submission status: Accepted

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

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.sort(key=lambda x:x[0])
for i in range(N):
    if K-ab[i][1]>0:
        K-=ab[i][1]
    else:
        print(ab[i][0])
        break

Submission status: Accepted

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

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

numList = []
for _ in range(N):
    numList.append(list(map(int, input().split())))

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

idx = 0
while True:
    K = K - numList[idx][1]
    if K <= 0:
        print(numList[idx][0])
        exit()
    idx = idx + 1