Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N, M = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(1)][0]
A.sort(reverse=True)
high = A[0:M]
low = A[M:]

while M != 0:
    high[0] = high[0] // 2
    high.sort(reverse=True)
    M -= 1

print(sum(high) + sum(low))

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(1)][0]
A = [-1*x for x in A]

import heapq
heapq.heapify(A)

while M != 0:
    x = heapq.heappop(A)
    y = -x // 2
    heapq.heappush(A, -y)
    M -= 1

A = [-1*x for x in A]
print(sum(A))
### BUGGY CODE ###

n = int(input())
plist = list(map(int,input().split()))


counter = 0

for i in range(len(plist)):
    islow = True
    for j in range(plist.index(plist[i])):        
        if plist[i] <= plist[j]:
            pass
        else:
            islow = False
            break
    if islow:
        counter += 1

print(counter)    

### FIXED CODE ###

n = int(input())
plist = list(map(int,input().split()))

islow = True
counter = 0
min = 0

for i in range(len(plist)):
    islow = True
    if i == 0:
        counter += 1
        min = plist[i]
        current_min = i
    elif min > plist[i]:
        counter += 1
        min = plist[i]
        current_min = i
        
print(counter)
### BUGGY CODE ###

#1:初期化
N, K = map(int,input().split())
h = list(map(int, input().split()))
#h = [int(x) for x in input().split()] #こっちのほうが早い？
inf = float("inf")
dp = [0]*(N)

#2:初期値
dp[0] = 0

#3:dp実行部(貰うDP)
for i in range(1,N):
    L = [dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-K),i)]
    dp[i] = min(L)
#    for k in range(1,min(N-i-1,K)+1):
#        dp[i+k] = min(dp[i+k], dp[i] + abs(h[i] - h[i+k]))
        #print(dp,i,k)

#4:出力
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*- 
def cost(h,N,K):
    dp=[0]*N
    dp[1]=abs(h[0]-h[1])
    for i in range(2,N):
        tmp=[abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i)]
        dp[i]=min(tmp)
    return dp[-1]

N,K=map(int,input().split())
h=[int(num) for num in input().split()]

print(cost(h,N,K))
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]

A_set = list(set(A))
ans = 0
for i in range(len(A_set)):
  nm = A_set[i]
  nm_cnt = A.count(nm)
  if nm_cnt < nm:
    ans += nm_cnt
  elif nm_cnt > nm:
    ans += nm_cnt - nm
  else:
    continue

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]

ans = 0
C = [0] * N # [1の個数, 2の個数, 3の個数, ... , Nの個数]
for i in range(N):
  n = A[i]
  if n <= N:
    C[n-1] += 1
  else: # n > N:
    ans += 1

for i in range(N):
  cnt = C[i]
  if cnt > i+1:
    ans += (cnt - (i+1))
  elif cnt < i+1:
    ans += cnt

print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

pin = []
for i in range(10):
    for j in range(10):
        for k in range(10):
            pin.append(str(i)+str(j)+str(k))

count = 0
for i in range(len(pin)):
    l, m, n = pin[i][0], pin[i][1], pin[i][2]
    l_idx, m_idx, n_idx = -1, -1, -1
    for i in range(N):
        if S[i] == l:
            l_idx = i
            break
    if l_idx != -1:
        for i in range(l_idx+1, N):
            if S[i] == m:
                m_idx = i
                break
    if m_idx != -1:
        for i in range(m_idx+1, N):
            if S[i] == n:
                n_idx = i
                break
    if l_idx != -1 and m_idx != -1 and n_idx != -1:
        count += 1

print(count)

### FIXED CODE ###

N = int(input())
S = input()

pin = []
for i in range(10):
    for j in range(10):
        for k in range(10):
            pin.append(str(i)+str(j)+str(k))

count = 0
for i in range(len(pin)):
    l, m, n = pin[i][0], pin[i][1], pin[i][2]
    l_idx, m_idx, n_idx = -1, -1, -1
    for i in range(N):
        if S[i] == l:
            l_idx = i
            break
    if l_idx != -1:
        for i in range(l_idx+1, N):
            if S[i] == m:
                m_idx = i
                break
    if m_idx != -1:
        for i in range(m_idx+1, N):
            if S[i] == n:
                n_idx = i
                break
    if l_idx != -1 and m_idx != -1 and n_idx != -1:
        count += 1

print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
r, g, b, n = map(int, input().split())

nr_max = n // r
ng_max = n // g

count = 0
for i in range(0, nr_max + 1):
    tmp1 = r * i
    if tmp1 == n:
        count += 1
    if tmp1 >= n:
        break
    for j in range(0, ng_max + 1):
        tmp2 = g * j + tmp1
        if tmp2 == n:
            count += 1
        if tmp2 >= n:
            break
        if (n - tmp2) % b == 0:
            count += 1

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
r, g, b, n = map(int, input().split())

nr_max = n // r
ng_max = n // g

count = 0
for i in range(nr_max + 1):
    tmp1 = r * i
    if tmp1 == n:
        count += 1
        break
    res = n - tmp1
    for j in range(res // g + 1):
        tmp2 = g * j + tmp1
        if tmp2 == n:
            count += 1
        if tmp2 >= n:
            break
        if (n - tmp2) % b == 0:
            count += 1

print(count)
### BUGGY CODE ###

I,*U=N,*D,=9**9,
P,*L='x+y,',
M,*R='x-y,',
for t in[*open(0)][1:]:*z,u=t.split();exec(u+'+=[*map(int,z)],')
for*A,S in(D,U,'x,y,'),(L,R,'y,x,'),(U,R,P+M),(L,D,P+M),(L,U,M+P),(D,R,M+P):
  n=I
  for x,y,r in eval('sorted((%sQ)for Q,P in enumerate(A)for x,y in P)'%S):exec(r*'n,p=x,y'or'N=min(N,y-p)'*(x==n))
print(N%I*5or'SAFE')

### FIXED CODE ###

d=[[],[],[],[]]
for t in[*open(0)][1:]:*z,u=t.split();d[ord(u)%5]+=[*map(int,z)],
I=N=9**9
P,M='x+y,','x-y,'
for*A,S in(3,0,'x,y,'),(1,2,'y,x,'),(0,2,P+M),(1,3,P+M),(1,0,M+P),(3,2,M+P):
 n=p=-I
 for x,y,r in eval('sorted((%sQ)for Q,P in enumerate(A)for x,y in d[P])'%S):
  if r:n,p=x,y
  elif x==n:N=min(N,y-p)
print(N%I*5or'SAFE')
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    X, Y, Z, K = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=True)
    B = sorted(list(map(int, input().split())), reverse=True)
    C = sorted(list(map(int, input().split())), reverse=True)
    MAX = 500

    res = []
    for i in range(min(len(A), MAX)):
        for j in range(min(len(B), MAX)):
            for k in range(min(len(C), MAX)):
                res.append(A[i] + B[j] + C[k])
    res.sort(reverse=True)
    for i in range(K):
        print(res[i])


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    AB = []
    for i in range(X):
        for j in range(Y):
            AB.append(A[i] + B[j])
    AB.sort(reverse=True)

    res = []
    for i in range(min(K, len(AB))):
        for j in range(Z):
            res.append(AB[i] + C[j])
    res.sort(reverse=True)

    for i in range(K):
        print(res[i])


if __name__ == '__main__':
    resolve()
### BUGGY CODE ###

import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_I(): return map(int, stdin)
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####		
def main():
	N,K = LI()
	A = LI()
	set_A = set(A)
	d = {}
	for a in set_A:
		d[a] = A.count(a)

	ans=0
	max_v,max_k = max((v,k) for (k,v) in d.items())
	while len(d)>K:
		min_v,min_k = min((v,k) for (k,v) in d.items())
		d[max_k] += min_v
		ans += min_v
		del d[min_k]

	print(ans)


if __name__ == '__main__':
	main()

### FIXED CODE ###

import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_I(): return map(int, stdin)
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####		
def main():
	N,K = LI()
	A = LI()

	cnt_d=defaultdict(lambda: 0)
	for i in A:
		cnt_d[i] += 1
	
	sorted_d = sorted(cnt_d.items(), key=lambda x: x[1])
	
	ans=0
	i=0
	n = len(cnt_d)
	while n>K:
		min_k,min_v = sorted_d[i]
		i+=1
		ans+=min_v
		n-=1

	print(ans)


if __name__ == '__main__':
	main()
### BUGGY CODE ###

import math

def permutations_count(n, r):
    return math.factorial(n) // ( math.factorial(n - r) * math.factorial(r) )


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

data = [0] * (N+1)

for i in range(N):
    data[A[i]] += 1

total = 0

for i in range(N+1):
    if data[i] >= 2:
        total += permutations_count(data[i],2)



for i in range(N):
    t = total
    if data[A[i]] - 1 > 0 :
        print( total-permutations_count(data[A[i]]-1,1) )
    else:
        print(total)

### FIXED CODE ###

import math
 
def permutations_count(n, r):
    if r == 2:
        return int( (n*(n-1) ) / r )
    if r == 1:
        return n
 
 
N = int(input())
A = list(map(int,input().split()))
 
data = [0] * (N+1)
 
for i in range(N):
    data[A[i]] += 1
 
total = 0
 
for i in range(N+1):
    if data[i] >= 2:
        total += permutations_count(data[i],2)
 
 
 
for i in range(N):
    if data[A[i]] - 1 > 0 :
        print( total - permutations_count(data[A[i]]-1,1) )
    else:
        print(total)
### BUGGY CODE ###

n,k = map(int,input().split())
r,s,p = map(int,input().split())
t = list(input())
leng = len(t)
ans = 0
dic = {"r":0, "s":0, "p":0, "cr":0, "cs":0, "cp":0}


for i in range(leng):
    if i >= k:
    
        if t[i] == t[i-k]:
            check = 2
            while True:
                if i < k*check:
                    break
                
                if t[i] == t[i-k*check]:
                    check += 1
                    continue
                else:
                    break
            
            if check%2 == 0:
                continue
            else:
                pass
        
    if t[i] == "r":
        ans += p
        dic["r"] = 1
        dic["cr"] = i
        
    elif t[i] == "s":
        ans += r
        dic["s"] = 1
        dic["cs"] = i

        
    elif t[i] == "p":
        ans += s
        dic["p"] = 1
        dic["cp"] = i
        
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
r,s,p = map(int, input().split())
t = list(input())

ans = 0

for i in range(n):
    valian = t[i]
    if valian == 'r':
        ans += p
    elif valian == 's':
        ans += r
    else:
        ans += s
        
for i in range(k):
    check = ''
    for j in range(i, n, k):
        if check == '':
            check = t[j]
            continue
        
        if check == t[j]:
            if t[j] == 'r':
                ans -= p
            elif t[j] == 's':
                ans -= r
            else:
                ans -= s
            check = ''
        else:
            check = t[j]
        
print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())
P = np.array(input().split(' '), dtype = int)

counta = 0
for i in range(N):
    counta += np.any((P[:i+1] < P[i]))
print(N - counta)

### FIXED CODE ###

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = list(map(int, input().split(' ')))

p_min = P[0]
ans = 0
for p in P:
    if p <= p_min:
        p_min = p
        ans += 1
print(ans)
### BUGGY CODE ###

import numpy as np

n=int(input())
v=list(map(int,input().split()))

e=np.array([v[i] for i in range(0,n,2)])
o=np.array([v[i] for i in range(1,n,2)])

se=set(e)
so=set(o)


if(len(se)==1 and len(so)==1):
    if(e[0]==o[0]):print(n//2)
    else:print(0)
    exit()

le=[]


for ve in se:
    a=len(e[e != ve])
    le.append([a,ve])

lo=[]
for vo in so:
    a=len(o[o != vo])
    lo.append([a,vo])
    
    
le.sort()
lo.sort()

if(len(se)==1):
    if(lo[0][1]!=le[0][1]):print(lo[0][0])
    else:print(lo[1][0])
elif(len(so)==1):
    if(lo[0][1]!=le[0][1]):print(le[0][0])
    else:print(le[1][0])
else:
    if(lo[0][1]!=le[0][1]):print(le[0][0]+lo[0][0])
    else:print(min(le[1][0]+lo[0][0],le[0][0]+lo[1][0]))

### FIXED CODE ###

import numpy as np
import collections

n=int(input())
v=list(map(int,input().split()))

e=np.array([v[i] for i in range(0,n,2)])
o=np.array([v[i] for i in range(1,n,2)])

se=set(e)
so=set(o)


lle=collections.Counter(e)
llo=collections.Counter(o)
le=[]
for k,v in lle.items():
    le.append([n//2-v,k])
lo=[]
for k,v in llo.items():
    lo.append([n//2-v,k])
le.sort()
lo.sort()

if(len(lle)==1 and len(llo)==1):
    if(e[0]==o[0]):print(n//2)
    else:print(0)
    exit()




if(len(se)==1):
    if(lo[0][1]!=le[0][1]):print(lo[0][0])
    else:print(lo[1][0])
elif(len(so)==1):
    if(lo[0][1]!=le[0][1]):print(le[0][0])
    else:print(le[1][0])
else:
    if(lo[0][1]!=le[0][1]):print(le[0][0]+lo[0][0])
    else:print(min(le[1][0]+lo[0][0],le[0][0]+lo[1][0]))
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([10^10 if i =="." else -1 for i in s])

dq = deque()
dq.append((Ch,Cw))
S[Ch][Cw]=0

while dq:
  a=dq.pop()
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and abs(i-2)+abs(j-2)==1:
        S[a[0]-2+i][a[1]-2+j]=min(S[a[0]][a[1]],S[a[0]-2+i][a[1]-2+j])
        dq.appendleft((a[0]-2+i,a[1]-2+j))
      elif a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W:
        S[a[0]-2+i][a[1]-2+j]=min(S[a[0]][a[1]]+1,S[a[0]-2+i][a[1]-2+j])
        dq.append((a[0]-2+i,a[1]-2+j))

print(S[Dh][Dw])

### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([10**10 if i =="." else -1 for i in s])
visit=[[False for i in range(W)] for j in range(H)]

dq = deque()
dq.append((Ch,Cw,0))
S[Ch][Cw]=0
counter=0

while dq:
  a=dq.popleft()
  if visit[a[0]][a[1]]==True:
    continue
  elif S[a[0]][a[1]]==counter:
    visit[a[0]][a[1]]=True
  elif a[2]==counter+1:
    visit[a[0]][a[1]]=True
    counter+=1
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W:
        if abs(i-2)+abs(j-2)==1 and S[a[0]][a[1]]<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter
          dq.appendleft((a[0]-2+i,a[1]-2+j,counter))
        elif S[a[0]][a[1]]+1<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter+1
          dq.append((a[0]-2+i,a[1]-2+j,counter+1))
  #print(visit,counter,a,dq,"\n")
if S[Dh][Dw]==10**10:
  print(-1)
else:
  print(S[Dh][Dw])
### BUGGY CODE ###

def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


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


def main():
    num_nodes, num_regions = tuple(input_ints())
    regions = [tuple(input_ints()) for _ in range(num_regions)]

    nodes = set()
    for r in regions:
        nodes.add(r[0])
        nodes.add(r[1])

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

    i = 0
    while i < len(regions):
        regions[0:i+1] + [r for r in regions[i+1:] if not (regions[i][0] <= r[0] and r[1] <= regions[i][1])]
        i += 1

    def solve(rs, steps):
        min_steps = 99999999999

        for i in [i for i in range(rs[0][0], rs[0][1]) if i in nodes]:
            rs2 = [r for r in rs if not r[0] <= i < r[1]]
            if rs2:
                min_steps = min(solve(rs2, steps + 1), min_steps)
            else:
                return steps

        return min_steps

    print(solve(regions, 1))


main()


### FIXED CODE ###

def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


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


def main():
    num_nodes, num_regions = tuple(input_ints())
    regions = [tuple(input_ints()) for _ in range(num_regions)]
    regions.sort(key=lambda r: r[1])

    edges = []
    for r in regions:
        if not edges or edges[-1] < r[0]:
            edges.append(r[1] - 1)

    print(len(edges))


main()
### BUGGY CODE ###

def main():
    N=int(input())
    L=list(map(int,input().split()))
    L_i,L_j=[],[]
    d, s = [0]*N, 0
    cnt=0
    
    for i, j in enumerate(L):
        if i+j<N:
            L_i.append(i+j)
        if i-j>0:
            L_j.append(i-j)

    for i in L_j:
        cnt += L_i.count(i)
        
    print(cnt)
main()

### FIXED CODE ###

def main():
    N=int(input())
    L=list(map(int,input().split()))
    L_i,L_j=[],[]
    L_memo = [0]*N
    cnt=0
    for i, j in enumerate(L):
        if i+j<N:
            L_memo[i+j]+=1
        if i-j>0:
            cnt+=L_memo[i-j]        
    print(cnt)
main()
### BUGGY CODE ###

def main():
    from itertools import product
    H, W, K = map(int, raw_input().split())
    G = [list(map(int, list(raw_input()))) for _ in range(H)]

    ans = float('inf')
    for pattern in product([0, 1], repeat=H-1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        counts = [0] * len(rows)
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]
                if counts[i] > K:
                    tmp_ans += 1
                    counts = [0] * len(rows)
                    break
            else:
                w += 1

        tmp_ans += len(div) - 2
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    from itertools import product
    H, W, K = map(int, input().split())
    G = [list(map(int, list(input()))) for _ in range(H)]

    ans = float('inf')
    for pattern in product([0, 1], repeat=H - 1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        d = set()
        df = False
        counts = [0] * len(rows)
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]

            if [c for c in counts if c > K]:
                if w in d:
                    df = True
                    break
                d.add(w)
                tmp_ans += 1
                counts = [0] * len(rows)
            else:
                w += 1

            if df:
                break
        
        if not df:
            tmp_ans += len(div) - 2
            ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
B = [0] + [int(input()) for _ in range(N)]

x = 1
cnt = 0
while True:
  x = B[x]
  cnt += 1
  if x == 2:
    break
  if x == 1:
    cnt = -1
    break
print(cnt)


### FIXED CODE ###

N = int(input())
B = [0] + [int(input()) for _ in range(N)]

x = 1
cnt = 0
dic = {x}
while True:
  x = B[x]
  cnt += 1
  if x == 2:
    break
  if {x} <= dic:
    cnt = -1
    break
  dic.add(x)
print(cnt)
### BUGGY CODE ###

n,k=map(int,input().split())
l=[]
for i in range(n):
  a,b=map(int,input().split())
  for j in range(b):
    l.append(a)
l=sorted(l)
print(l[k-1])

### FIXED CODE ###

n,k=map(int,input().split())
li = [list(map(int, input().split())) for i in range(n)]
li.sort()
c=0
for i in range(n):
  c+=li[i][1]
  if c>=k:
    print(li[i][0])
    
    break
### BUGGY CODE ###

from fractions import gcd

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)

ans = 0
for a in A:
    ans = (ans + lcm_ // a) % (10 ** 9 + 7)

print(ans)

### FIXED CODE ###

from fractions import gcd

M = 10 ** 9 + 7

def xgcd(a, b):
    x0, x1 = 1, 0
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
    return x0 % M

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)

ans = 0
for a in A:
    m = xgcd(a, M)
    ans = ans + lcm_ * m

print(ans % M)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
s = [1]*(n+1)

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    if i >= 0:
        s[i+2] = (s[i+1] + s[i]) % (10**9+7)

print(s[-1])

### FIXED CODE ###

n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    s[i+2] = (s[i+1] + s[i]) % (10**9+7)
    
print(s[-1])
### BUGGY CODE ###

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

inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(N):
    A, B = map(int, input().split())
    for j in range(H):
        t1 = j + A
        if t1 > H:
            t1 = H
        t2 = dp[j] + B
        if t2 < dp[t1]:
            dp[t1] = t2
print(dp[H])


### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
ans = 0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i] + L[j] > L[k]:
                ans += 1
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
ans = 0

for i in range(N-2):
    for j in range(i+1,N-1):
        ans += bisect.bisect_left(L,L[i]+L[j]) - j - 1
print(ans)