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: Runtime Error

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

d = dict()

for i in range(N):
    a, b = list(map(int, input().split(" ")))
    if a in d:
        d[a] = d[a] + b
    else:
        d[a] = b
    
ans_sum = 0

for key in sorted(d.keys()):
    ans_sum += d[key]
    if (ans_sum) >= K:
        print(k)
        break

Submission status: Runtime Error

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

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

print(nums[k-1])

Submission status: Runtime Error

Solution code:
    A = [0 for _ in xrange(10**5+10)]
    N, K = map(int, raw_input().split())
    for i in xrange(N):
        a, b = map(int, raw_input().split())
        A[a] += b
     
    k = 0
    for i in xrange(10**5+10):
        k += A[i]
        if k >= K:
            print i
            break

Submission status: Runtime Error

Solution code:
for i in range(x[0]+1):
    a, b= map(int , input().split())
    v[a]+=b


diffK=x[1]

for i in range(1,x[0]+1):
    if diffK-v[i]<=0:
        print(i)
        quit()
    else:
        diffK -=v[i]

Submission status: Runtime Error

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



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

        quit()
    else:
        diffK -=i[1]

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
string = ''
for i in range(n):
    a,b=(input().split())
    string += a*int(b)
string = [int(i) for i in string]
print(sorted(string)[k-1])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
string = ''
for i in range(n):
    a,b=(input().split())
    string += a*int(b)
string = [int(i) for i in string]
print(sorted(string[k-1]))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
string = ''
for i in range(N):
    a,b=(input().split())
    string += a*int(b)
print(string[k-1])

Submission status: Runtime Error

Solution code:
# N,Kの把握
l1 = list(map(int, input().split()))
N = l1[0]
K = l1[1]

#空リストを作成。a,bを把握し、リストにaを追加、b回。これをN回くりかえし
l3 = []
for i in range(N):
	l2 = list(map(int, input().split()))
	a = l2[0]
	b = l2[1]
	if b <= K:
		for j in range(b):
			l3.append(a):
	else
		for j in range(K):
			l3.append(a)

# リストをソートし、K番目を出力
l3.sort()
print(str(l3[K-1]))

Submission status: Runtime Error

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

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

x.sort()
print(x[k-1])

Submission status: Runtime Error

Solution code:
tmp = input().split(" ")
N = int(tmp[0])
K = int(tmp[1])

num = [0 for i in range(N)] 
for i in range(N):
    tmp = input().split(" ")
    a = int(tmp[0])
    b = int(tmp[1])
    num[a-1] = num[a-1] + b

tmp = 0
i = 0
while tmp < K:
    tmp = tmp + num[i]
    if tmp >= K:
        print(i+1)
    i = i + 1

Submission status: Runtime Error

Solution code:
tmp = input().split(" ")
N = int(tmp[0])
K = int(tmp[1])

num = [0 for i in range(N-1)] 
for i in range(N-1):
    tmp = input().split(" ")
    a = int(tmp[0])
    b = int(tmp[1])
    num[a-1] = num[a-1] + b

tmp = 0
i = 0
while tmp <= K:
    tmp = tmp + num[i]
    if tmp >= K:
        print(i+1)
    i = i + 1

Submission status: Runtime Error

Solution code:
tmp = input().split(" ")
N = int(tmp[0])
K = int(tmp[1])

num = [0 for i in range(N-1)] 
for i in range(N):
    tmp = input().split(" ")
    a = int(tmp[0])
    b = int(tmp[1])
    num[a-1] = num[a-1] + b

tmp = 0
i = 0
while tmp <= K:
    tmp = tmp + num[i]
    if tmp >= K:
        print(i+1)
    i = i + 1

Submission status: Runtime Error

Solution code:
tmp = input().split(" ")
N = int(tmp[0])
K = int(tmp[1])

num = [0 for i in range(N)] 
for i in range(N):
    tmp = input().split(" ")
    a = int(tmp[0])
    b = int(tmp[1])
    num[a-1] = num[a-1] + b

tmp = 0
i = 0
while tmp <= K:
    tmp = tmp + num[i]
    if tmp >= K:
        print(i+1)
    i = i + 1

Submission status: Runtime Error

Solution code:

a,b=map(int,input().split())
alllist=[]
goukei=0
for i in range(a):
    tmplist=list(map(int,input().split()))
    alllist.append(tmplist)

alllist2=sorted(alllist)
for i in range(a):
    goukei=alllist2[i][1]+goukei
    if goukei>b:
        owari=alllist2[i][0]
        break
    else:
        pass

print(owari)

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())
alllist=[]
goukei=0
for i in range(a):
    tmplist=list(map(int,input().split()))
    alllist.append(tmplist)
    
sorted(alllist)
for i in range(a):
    goukei=alllist[a][1]+goukei
    if goukei>b:
        owari=alllist[a][0]
        break
    else:
        pass

print(owari)

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split())

goukei=0
for i in range(a):
    aN,bN=map(int,input().split())
    goukei=bN+goukei
    if goukei>b:
        owari=aN
        break
    else:
        pass

print(owari)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
U = []
for i in range(n):
    U.append(tuple(map(int, input().split())))
sorted(U, key=lambda i: i[0])
# print(U)
for i in U:
    k -= i[1]
    print(i, k)
    if k <= 0:
        print(i[0])
        return

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, K = map(int, raw_input().split())
R = [0] * (10**5) 

for i in xrange(N):
     ia, ib = map(int, raw_input().split())
     R[ia] += ib

k = 0
c = 0
while k < K:
    c += 1
    k += R[c]
print c

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import numpy as np
N, K = map(int, raw_input().split())

def test():
    ia, ib = map(int, raw_input().split())
    return np.ones(ib) * ia

R = np.array([test() for i in xrange(N)])
print int(np.sort(R.flatten())[K-1])

Submission status: Runtime Error

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

c = []

for i in range(N):
	c.append(input().split())

d = []
e = []

for j in range(N):
	e.append(c[j][0])
	e = e * c[j][1]
	d = d + e
	e = []

d.sort()

print(d[K-1])

Submission status: Runtime Error

Solution code:
#N,Kの取得
N,K = list(map(int,input().split()))

#[(a_1,b_1),(a_2,b_2),...]の形でリストを作成
numList = [ map(int,input().split()) for _ in range(N) ]

#作成したリストを、aの大きさで昇順ソート
numList = sorted(numList,key=lambda x:x[0])

#小さい順に要素数bを足していき、Kを超えた段階で出力、終了
count = 0
for a,b in numList:
	count += b
	if count>=K:
		print(a)
		quit()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import numpy as np
N, K = map(int, raw_input().split())
R = []
for i in xrange(K):
    ia, ib = map(int, raw_input().split())
    R.extend([ia, ib])

R = sorted(R)
R.reverse()

count = 1
c = 0
r = R.pop()

for i in xrange(N):
    while count == r and len(R) > 0:
        c += 1
        r = R.pop()

    print c
    count += 1
    c = 0

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import collections
r = [0]*100000
n,k = [int(x) for x in sys.stdin.readline().split()]
for i in range(n):
	a, b = [int(x) for x in sys.stdin.readline().split()]
	r[a] += b
c = 0
for i,j in enumerate(r):
	c += j
	if c >= k:
		print(i)
		break

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import collections
n,k = [int(x) for x in sys.stdin.readline().split()]
r = np.zeros(10**5)
for i in range(n):
	a, b = [int(x) for x in sys.stdin.readline().split()]
	r[a] += b
c = 0
for i,j in enumerate(r):
	c += j
	if c >= k:
		print(i)
		break

Submission status: Runtime Error

Solution code:
n,k = map(int,raw_input().split())
l = []
s = list()
for i in range(n):
    v,count = map(int,raw_input().split())
    l.append((count,v))

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

countTmp = 0
for count,v in l:
    count >= k:
        print v
        break
    countTmp = countTmp + count
    if k <= countTmp:
       print v
       break;

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = list(map(int, input().split(' ')))
L = np.zeros(N).astype(int)
for _ in range(N):
    a, b = list(map(int, input().split(' ')))
    L[a-1] += b
    
tot = 0
for i in range(N):
    tot += L[i]
    if tot >= K:
        break
print(i+1)

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = list(map(int, input().split(' ')))
L = np.zeros(N).astype(int)
for _ in range(N):
    a, b = list(map(int, input().split(' ')))
    L[a-1] += b
    
tot = 0
for i in range(N):
    tot += L[i]
    if tot >= K:
        print(i+1)
        break

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = list(map(int, input().split(' ')))
L = np.zeros(N).astype(int)
for _ in range(N):
    a, b = list(map(int, input().split(' ')))
    L[a-1] += b
    
tot = 0
for i in range(N):
    tot += L[i]
    if tot >= K:
        print(i)
        break

Submission status: Runtime Error

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

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

ls.sort()
for a,b in ls:
    if b >= k:
        print(x)
        break
    else:
        k -= b

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import collections
n,k = [int(x) for x in sys.stdin.readline().split()]
r = collections.defaultdict(int)
for i in range(n):
	a, b = [int(x) for x in sys.stdin.readline().split()]
	r[a] += b
d = sorted(r.items())
c = 0
for i,j in enumerate(d):
	c += j
	if c >= k:
		print(int(i))
		break

Submission status: Runtime Error

Solution code:
import numpy as np
n,k=map(int,raw_input().split())
a=[]
b=[]
for i in range(n):
    aa,bb=map(int,raw_input().split())
    a.append(aa)
    b.append(bb)
a=np.array(a)
b=np.array(b)



c=np.cumsum(b)
z=c[c<k]
print(a[z[-1]-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

array = []
hoge  = []
n, k  = map(int, raw_input().split())

for i in xrange(n):
	a, b  = map(int, raw_input().split())
	array.append([a, b])

array.sort()
print(array)

for i in range(len(array)):
	hoge += array[i][0] * array[i][1]
	if len(hoge) >= k:
		break
print(hoge[k - 1])

Submission status: Runtime Error

Solution code:
import numpy as np
n,k = input().split()
n = int(n)
k = int(k)
l = list()
for i in range(n):
    a, b = input().split()
    l.append([int(a),int(b)])

ar = np.array(l)
ar_s = ar.sort(0)
count = np.cumsum(ar_s[:,1])

print(ar_s)
print(count)
print(int(ar_s[np.where(count >=k)[0][0]][0]))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
ls = []
b_num = 0

for i in range(n):
    a,b = [int(i) for i in input().split()]
    if b_num < k:
        tmp = [a] * b
        ls.extend(tmp)
        #ls.sort()
        b_num += b
    else:
        if(a <= ls.max):
            tmp = [a] * b
            ls.extend(tmp)

ls.sort()
print(ls[k-1])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from collections import defaultdict as dd
n,k = [int(x) for x in sys.stdin.readline().split()]
r = dd(int)
for i in range(n):
	a, b = [int(x) for x in sys.stdin.readline().split()]
	r[a] += b
r.sort()
c = 0
for i,j in r.items():
	c += j
	if c >= k:
		print(i)
		break

Submission status: Runtime Error

Solution code:

N,K = map(int, input().split())
ab_list = {}
for i in range(N):
    a,b = map(int, input().split())
    akagi=str(a)
    if akagi in ab_list:
        ab_list[akagi] += b
        print("if")
        print(ab_list)
    else:
        ab_list[akagi] = b
        print("else")
        print(ab_list)
        

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

array = []
hoge  = []
n, k  = map(int, raw_input().split())

for i in xrange(n):
	a, b  = map(int, raw_input().split())
	array.append(a)

array.sort()
for i in array:
	hoge += [array[i]] * b
	if len(hoge) >= k:
		break


print(hoge[k - 1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

array = []
hoge  = []
n, k  = map(int, raw_input().split())

for i in xrange(n):
	a, b  = map(int, raw_input().split())
	array.append(a)

array.sort()
for i in array
	hoge += [array[i]] * b
	if len(hoge) >= k:
		break


print(hoge[k - 1])

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
ls = []
b_num = 0

for i in range(n):
    a,b = [int(i) for i in input().split()]
    if b_num <= b:
        tmp = [a] * b
        ls.extend(tmp)
        ls.sort
        b_num += b
    else:
        if(a < ls[-1]):
            tmp = [a] * b
            ls.extend(tmp)
            ls.sort
        
print(ls[k-1])

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
ls = []
b_num = 0

for i in range(n):
    a,b = [int(i) for i in input().split()]
    if b_num <= b:
        tmp = [a] * b
        ls.extend(tmp)
        ls.sort
        b_num += b
    else:
        if(a < ls[-1]):
            tmp = [a] * b
            ls.extend(tmp)
            ls.sort
            b_num += b  
        
print(ls[k-1])

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
ls = []
b_num = 0

for i in range(n):
    a,b = [int(i) for i in input().split()]
    if b_num <= b:
        tmp = [a] * b
        ls.extend(tmp)
        ls.sort
        b_num += b
    else:
        if(a > ls[-1]):
            break
        else:
            tmp = [a] * b
            ls.extend(tmp)
            ls.sort
            b_num += b  
        
print(ls[k-1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

res=np.array([1000000]*K)
for row in [list(map(int,input().split())) for _ in [1]*N]:
    for _ in [1]*int(row[1]):
        res.sort()
        if row[0]<res[K-1]:res[K-1]=row[0]
res.sort()

print(res[len(res)-1])

Submission status: Runtime Error

Solution code:
N, K = map(int, raw_input().split())
array=[10^5+1]*K
for i in range(N):
 a,b=map(int, raw_input().split())
 for j in range(K):
  if a<array[j] and 0<b:
   array[j]=a
   b=b-1
array.sort()
print array[K-1]

Submission status: Runtime Error

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

for i in range(n):
    a,b = [int(i) for i in input().split()]
    tmp = [a] * b
    ls.append(tmp)

ls = sum(ls,[])
ls.sort(k-1)
print(ls)

Submission status: Runtime Error

Solution code:
N, K = [int(x) for x in input().split()]
Array = list()
A = list()
count = 0
ans = 0
for i in range(N):
	A.append[int(x) for x in input().split()]

A.sort(key=itemgetter(0), reverse=True)
for i in range(N):
	count += A[1, i]
	if count >= K:
		ans = A[0, i]
		break
		
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
n,k = [int(x) for x in sys.stdin.readline().split()]
r = np.array()
for i in range(n):
	r[i] = [int(x) for x in sys.stdin.readline().split()]
r.sort(key=lambda x:x[0])
c = 0
for i,j in enumerate(r):
	c += j[0]
	if c >= k:
		print(j[1])
		break

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, k = map(int, raw_input().split())
sum = 0
array = []
for i in range(n):
    a, b = map(int, raw_input().split())
    sum += b
    if k <= sum:
        break
    for j in range(b):
        array.append(a)

array.sort()
print array[k]

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=[]
C=[]
for i in range(N):
    a,b=map(int,input().split())
    T=[a,b]
    A.append(T)
A.sort()
counter=0
for i in range(N):
     counter+=A[i][1]
     if counter>K:
         counter=i
         break
print(A[counter-1][0])

Submission status: Runtime Error

Solution code:
import sys
N,K=map(int, input().split())
p=[]
for i in range (0,N):
  r=list(map(int, input().split() )) 
  p.append(r)
p.sort()
k=0
for i in range(0,N):
  k+=p[i][0]]
  if k>=K:
    print(p[i][1])
    sys.exit()
import sys
N,K=map(int, input().split())
p=[]
for i in range (0,N):
  r=list(map(int, input().split() )) 
  p.append(r)
p.sort()
k=0
for i in range(0,N):
  k+=p[i][1]
  if k>=K:
    print(p[i][0])
    sys.exit()

Submission status: Runtime Error

Solution code:
mport numpy as np

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

a = []
array = np.array([])
for i in range(N):
    a = list(map(int,input().split()))
    array = np.concatenate((array,a[0]*np.ones(a[1])))
print (array)
array = np.sort(array)

print (int(array[K-1]))

Submission status: Runtime Error

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

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

ends = [0 for x in range(10**5)]
for a, b in ab:
    ends[a] += b
    
    k -= b
    if k <= 0:
        break


for i, e in enumerate(ends):
    tk -= e
    if tk <= 0:
        print(i)
        break

Submission status: Runtime Error

Solution code:
import sys
N,K=map(int, input().split())
p=[]
for i in range (0,N):
  r=list(map(int, input().split() )) 
  p.append(r)
p.sort()
q=[]
for i in range(0,N):
  q+=[p[i][0]]*p[i][1]
  if len(q)>K;
    print(q[K-1])
    sys.exit()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

array = []
n, k  = map(int, raw_input().split())

for i in range(n):
	a, b = map(int, raw_input().split())
	array.append(a)
	array.append(b)

array.sort()
print(array[k - 1])

Submission status: Runtime Error

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

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

for i in range(N):
    count+=b[i]
    if count>=K:
        print a[i]
        break