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

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    res = 0
    balls = {}

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1
    
    delList = []
    bucket = [0 for _ in range(n+1)]

    for a in A:
        bucket[a] += 1
    
    for i in range(len(bucket)):
        if bucket[i] == 0:
            bucket[i] = 10**9
    
    for _ in range(len(set(A))):
        minBucket = min(bucket)
        minBucketIdx = bucket.index(minBucket)
        delList.append(minBucketIdx)
        bucket[minBucketIdx] = 10**9

    while len(delList) > k:
        res += balls[delList[0]]
        delList.pop(0)
    
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    res = 0
    balls = {}
    bucket = [[] for _ in range(n+1)]

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1
    
    for key, value in balls.items():
        bucket[value].append(key)

    for i in range(len(bucket)):
        for j in range(len(bucket[i])):
            if bucket[i] != [] and len(balls) > k:
                res += i
                balls.pop(bucket[i][j])

    print(res)

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

import re
S = input()

result = 0
for i in range(len(S)):
    if re.search(r'01|10', S):
        result += 2
        S = re.sub(r'01|10', '', S, 1)
print(result)


### FIXED CODE ###

S = input()
temp0 = S[:int(len(S)/2)]
temp1 = S[int(len(S)/2):]
temp01 = min(temp0.count('0'), temp1.count('1'))
temp10 = min(temp0.count('1'), temp1.count('0'))
print(temp01 * 2 + temp10 * 2)
### BUGGY CODE ###

import sys
def main():
   input = sys.stdin.buffer.readline
   n,m = map(int, input().split())
   results = {}
   p_list=[]
   y_list=[]
   cnt = 0
   for i in range(m):
       p,y = map(int, input().split())
       p_list.append(p)
       y_list.append(y)
       if results.get(p) is None:
           results[p] = [y]
       else:
           results[p].append(y)
   for i in p_list:
       p_sort = sorted(results[i])
       print('{:006}'.format(i)+'{:006}'.format(p_sort.index(y_list[cnt])+1))
       cnt+=1
if __name__ == "__main__":
    main()

### FIXED CODE ###

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

convertedPY = [
    {'index': i,
     'city': py[0],
     'year': py[1]
     } for i, py in enumerate(PY)
]
'''
3 4
1 32
3 64
3 63
1 33

'''
convertedPY = sorted(convertedPY, key=lambda a: (a['city'], a['year']))
answer = []
cnt = 0
tmp = convertedPY[0]['city']
#print(convertedPY)
result = []
for py in convertedPY:
    #print(tmp)
    temp_dict = {}
    if tmp == py['city']:
        cnt += 1
        temp_dict['answer'] = '{:0=6}'.format(py['city']) + '{:0=6}'.format(cnt)
        temp_dict['index'] = py['index']
        result.append(temp_dict)
    else:
        cnt = 1
        temp_dict['answer'] = '{:0=6}'.format(py['city']) + '{:0=6}'.format(cnt)
        temp_dict['index'] = py['index']
        result.append(temp_dict)
        tmp = py['city']


result = sorted(result, key=lambda a: a['index'])
#print(result)
for r in result:
    print(r['answer'])

'''
3
21 -11
81234 52141 94124
'''

#print(PY)
### BUGGY CODE ###

import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]

N,M,Q = Is()
lis = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = Is()
    lis[l][r] += 1

cs = [[0]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        cs[i][j] = cs[i][j-1] + sum(lis[i][:j+1])

for _ in range(Q): 
    p,q = Is()
    t = 0
    for i in range(p,q+1):
        t += cs[i][q] - cs[i][q-1]
    print(t)

### FIXED CODE ###

import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]

N,M,Q = Is()
lis = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = Is()
    lis[l][r] += 1

cs = [[0]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        cs[i][j] = cs[i][j-1] + sum(lis[i][:j+1])

for _ in range(Q): 
    p,q = Is()
    t = 0
    for i in range(p,q+1):
        t += cs[i][q] - cs[i][q-1]
    print(t)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for a in range(k + 1):
    for b in range(k + 1):
        for c in range(k + 1):
            if a + b + c == s:
                count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for a in range(k + 1):
    for b in range(k + 1):
        if 0 <= s - (a + b) <= k:
            count += 1
print(count)
### BUGGY CODE ###

N=int(input())
word=set()
number=[]
S=list(map(int,input()))
for i in range(10):
    for j in range(10):
        for k in range(10):
           number.append([str(i)+str(j)+str(k)])
ans=0
for i in number:
    i,j,k=int(i[0][0]),int(i[0][1]),int(i[0][2])
    p1,p2,p3=-1,-1,-1
    for s in range(N):
        if S[s]==i and p1==-1:
            p1=s
        elif S[s]==j and p2<p1:
            p2=s
        elif S[s]==k and p3<p2:
            p3=s
            break
    if p1!=-1 and p2!=-1 and p3!=-1:
        if p1<p2<p3:
            ans+=1

print(ans)




### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

n, b, r = map(int, input().split())
x = []
bool = True
while bool:
    for i in range(b):
        if len(x) == n:
            bool = False
        else:
            x.append("b")
    for j in range(r):
        if len(x) == n:
            bool = False
        else:
            x.append("r")

print(x.count("b"))


### FIXED CODE ###

n, b, r = map(int, input().split())
b1 = n//(b+r)
b2 = n % (b+r)
if b == 0:
    print(0)
elif r == 0:
    print(n)
elif b2 != 0 and b2 <= b:
    b1 = b1*b + b2
    print(b1)
elif b2 != 0 and b2 > b:
    b1 = b1*b + b
    print(b1)
elif n % (b+r) == 0:
    print(b1*b)
### BUGGY CODE ###

N, M = map(int,input().split())
ab = [list(map(lambda s: int(s)-1, input().split()))for _ in range(M)]
prev = [0] * N
to_list = [[]for _ in range(N)]

for a,b in ab:
  to_list[a].append(b)
  to_list[b].append(a)

marked = [0]
stack = [0]

for i in stack:
    for j in to_list[i]:
        if j in marked: continue
        stack.append(j)
        marked.append(j)
        prev[j] = i

for i in range(N):
    if i == 0: 
        print('Yes')
        continue
    print(prev[i]+1)

### FIXED CODE ###

N, M = map(int,input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
prev = [0] * N
to_list = [ [] for _ in range(N)]

for a,b in AB:
  to_list[a - 1].append(b - 1)
  to_list[b - 1].append(a - 1)

marked = {0}
que = [0]

for i in que:
    for j in to_list[i]:
        if j in marked: continue
        que.append(j)
        marked.add(j)
        prev[j] = i+1

print('Yes')
print(*prev[1:], sep='\n')
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]


class BIT:
    def __init__(self, a, func=int.__add__, one=0):
        self.n = len(a)
        self.func = func
        self.one = one
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.func(self.a[i], x)
            i += i & (-i)

    def get(self, i):
        i += 1
        s = self.one
        while i != 0:
            s = self.func(s, self.a[i])
            i -= i & (-i)
        return s


ans = 10 ** 18
for i in range(1 << n):
    c = []
    for j in range(n):
        if i >> j & 1 == 0:
            c.append(a[j])
        else:
            c.append(b[j])
    d = sorted(c)

    ind = {}
    for j, k in enumerate(d):
        if (j % 2, k) not in ind:
            ind[(j % 2, k)] = j

    e = []
    ok = True
    for j, k in enumerate(c):
        j = ((i >> j & 1) + j) % 2
        if (j, k) not in ind:
            ok = False
            break
        l = ind[(j, k)]
        if l >= n or d[l] != k:
            ok = False
            break
        e.append(l)
        ind[(j, k)] += 2

    if ok:
        count = 0
        bit = BIT([0] * (n+1))
        for j in e:
            count += bit.get(n - j)
            bit.update(n-j, 1)
        ans = min(ans, count)
if ans == 10 ** 18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

ans = 10 ** 18
for i in range(1 << n):
    c = []
    for j in range(n):
        if i >> j & 1 == 0:
            c.append(a[j])
        else:
            c.append(b[j])
    d = sorted(c)

    ind = {}
    for j, k in enumerate(d):
        if (j % 2, k) not in ind:
            ind[(j % 2, k)] = j

    e = []
    ok = True
    for j, k in enumerate(c):
        j = ((i >> j & 1) + j) % 2
        if (j, k) not in ind:
            ok = False
            break
        l = ind[(j, k)]
        if l >= n or d[l] != k:
            ok = False
            break
        e.append(l)
        ind[(j, k)] += 2

    if ok:
        count = 0
        for _ in range(n):
            for j in range(n - 1):
                if e[j] > e[j + 1]:
                    count += 1
                    e[j], e[j + 1] = e[j + 1], e[j]
        ans = min(ans, count)
if ans == 10 ** 18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0
sums=[sum(sl[k:]) for k in range(len(sl))]
answers={}
def search(xx,yy,k,isUD):
    if (xx,yy,k) in answers:
        return answers[(xx,yy,k)]
    if k == len(sl):
        ans=(xx,yy)==(x,y)
    else:
        if abs(xx-x)+abs(yy-y) > sums[k]:
            ans=False
        else:
            lng=sl[k]
            # D or L
            llr=(lng if not isUD else 0)
            lud=(lng if isUD else 0)
            d_l = search(xx-llr,yy-lud,k+1, not isUD)
            u_r = search(xx+llr,yy+lud,k+1, not isUD)
            ans = d_l or u_r
    answers[(xx,yy,k)]=ans
    return ans
print('Yes' if search(x0,y0,1,True) else 'No')

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0
s_x = sl[::2]
s_y = sl[1::2]
s_y=[0]+s_y
dpx=[set() for i in s_x]
dpy=[set() for i in s_y]
dpx[0].add(s_x[0])
dpy[0].add(0)
for i,l in enumerate(s_x):
    if i==0:continue
    ll=dpx[i]
    for xx in dpx[i-1]:
        ll.add(xx-l)
        ll.add(xx+l)
for i,l in enumerate(s_y):
    if i==0:continue
    ll=dpy[i]
    for yy in dpy[i-1]:
        ll.add(yy-l)
        ll.add(yy+l)
print('Yes' if x in dpx[-1] and y in dpy[-1] else 'No')
### BUGGY CODE ###

import itertools

iCnt = int(input())
v = list(input())

vAns = []
vProduct = []
iOnIndex = 0
while iOnIndex + 1 < len(v):
    iLen = len(v[-len(v) + iOnIndex + 1:])
    vProduct = list(itertools.product([0, 1], repeat=iLen))
    for p in vProduct:
        sChk = v[iOnIndex]
        for i in range(len(p)):
            if p[i] == 1:
                if v[iOnIndex + i + 1] not in sChk:
                    sChk += v[iOnIndex + i + 1]
                else:
                    sChk = "NG"
        if "NG" not in sChk: vAns.append(sChk)
    iOnIndex += 1
vAns.append(v[len(v) - 1])
print(len(vAns) % (10 ** 9 + 7))

### FIXED CODE ###

from collections import defaultdict

iCnt = int(input())
S = input()
M = 10**9 + 7

vCntDct = defaultdict(int)

for s in S:
    vCntDct[s] += 1

ans = 1
for v in vCntDct.values():
    ans *= (v + 1)
    ans %= M

print(ans - 1)
### BUGGY CODE ###

import sys
# from collections import defaultdict
# from collections import Counter
# from queue import PriorityQueue
# sys.setrecursionlimit(2000000)

def distance(X, Y, start, goal):
    ans = float('inf')

    tmp = goal - start
    if tmp < ans:
        ans = tmp

    # start ~ X ~ Y ~ goal,
    tmp = abs(X - start) + 1 + abs(goal - Y)
    if tmp < ans:
        ans = tmp

    # start ~ Y ~ X ~ goal
    tmp = abs(Y - start) + 1 + abs(goal - X)
    if tmp < ans:
        ans = tmp

    return ans

#     # 短絡パスを使える場合
#     if start <= X and Y <= goal

#     # 短絡パスを使えないならば、普通に距離を計算
#     if X < start:
#         return goal - start

#     # 短絡パスを使えても、隣のパスへの距離は1
#     if goal - start == 1:
#         return 1

#     # 短絡パスより手前だと使えない
#     if goal < Y:
#         return goal - start



    # return goal - start - 1

def main():
    # N = int(input())

    N, X, Y = [int(s) for s in input().split()]

    distance_dict = {}
    for i in range(1, N+1):
        for j in range(i + 1, N+1):
            d = distance(X, Y, i, j)
            # sys.stderr.write('{} to {} : d = {}\n'.format(i, j, d))
            # ditance_dict[(i, j)] = d
            if d in distance_dict:
                distance_dict[d] += 1
            else:
                distance_dict[d] = 1

    for k in range(1, N):
        # print(str(distance_dict[k]))
        if k in distance_dict:
            print(distance_dict[k])
        else:
            print('0')
    # As = []
    # Bs = []
    # for i in range(N):
    #     A, B = [int(s) for s in input().split()]
    #     As.append(A)
    #     Bs.append(B)

    return 0

if __name__ == '__main__':
    sys.exit(main())


### FIXED CODE ###

import sys
from collections import defaultdict
# from collections import Counter
# from queue import PriorityQueue
# sys.setrecursionlimit(2000000)

def distance(X, Y, start, goal):
    ans = float('inf')

    tmp = goal - start
    if tmp < ans:
        ans = tmp

    # start ~ X ~ Y ~ goal,
    tmp = abs(X - start) + 1 + abs(goal - Y)
    if tmp < ans:
        ans = tmp

    # start ~ Y ~ X ~ goal
    tmp = abs(Y - start) + 1 + abs(goal - X)
    if tmp < ans:
        ans = tmp

    return ans

#     # 短絡パスを使える場合
#     if start <= X and Y <= goal

#     # 短絡パスを使えないならば、普通に距離を計算
#     if X < start:
#         return goal - start

#     # 短絡パスを使えても、隣のパスへの距離は1
#     if goal - start == 1:
#         return 1

#     # 短絡パスより手前だと使えない
#     if goal < Y:
#         return goal - start



    # return goal - start - 1

def main():
    # N = int(input())

    N, X, Y = [int(s) for s in input().split()]

    distance_dict = defaultdict(int)
    for i in range(1, N+1):
        for j in range(i + 1, N+1):
            d = distance(X, Y, i, j)
            # sys.stderr.write('{} to {} : d = {}\n'.format(i, j, d))
            # ditance_dict[(i, j)] = d
            distance_dict[d] += 1

    for k in range(1, N):
        # print(str(distance_dict[k]))
        print(distance_dict[k])

    # As = []
    # Bs = []
    # for i in range(N):
    #     A, B = [int(s) for s in input().split()]
    #     As.append(A)
    #     Bs.append(B)

    return 0

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

import itertools

S = input()[::-1]

m = [0]*len(S)
tmp = 1
for i in range(len(S)):
    m[i] = int(S[i])*tmp%2019
    tmp *= 10

cum = [0]+[0]*len(S)
for i in range(1,len(S)+1):
    cum[i] = (cum[i-1]+m[i-1])%2019

d = {}
ans = 0
for i in range(len(cum)):
    if cum[i] not in d:
        d[cum[i]] = 1
    else:
        ans += d[cum[i]]
        d[cum[i]] += 1
print(ans)

### FIXED CODE ###

import itertools

S = input()[::-1]

m = [0]*len(S)
tmp = 1
for i in range(len(S)):
    m[i] = int(S[i])*tmp%2019
    tmp = tmp*10%2019

cum = [0]+[0]*len(S)
for i in range(1,len(S)+1):
    cum[i] = (cum[i-1]+m[i-1])%2019

d = {}
ans = 0
for i in range(len(cum)):
    if cum[i] not in d:
        d[cum[i]] = 1
    else:
        ans += d[cum[i]]
        d[cum[i]] += 1
print(ans)
### BUGGY CODE ###

def solve():
    N = int(input())
    P = []
    for i in range(N):
        P.append(int(input()))

    # asc
    asc_num = 0
    target = 1
    _dict = {}
    for P_i in P:
        del_flag = False
        if P_i not in _dict.keys() and P_i not in _dict.values():
            _dict[P_i] = P_i + 1
        for k, v in _dict.items():
            if v == P_i:
                _dict[k] = P_i + 1 
            elif k-1 == P_i:
                asc_num = max(asc_num, v-k)
        if del_flag:
            del _dict[k]
    for k, v in _dict.items():
        asc_num = max(asc_num, v-k)

    print(N-asc_num)



if __name__ == '__main__':
    solve()

### FIXED CODE ###

N = int(input())
P = []
Q = [0 for i in range(N+1)]
for i in range(1, N+1):
    Q[int(input())] = i

straight = 1
max_straight = 1
for i in range(1, N):
    if Q[i] < Q[i+1]:
        straight += 1
        max_straight = max(straight, max_straight)
    else:
        straight = 1

print(N - max_straight)
### BUGGY CODE ###

from collections import deque

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

S = [list(input()) for i in range(H)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

start = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            start.append((i,j))

def distance(i,j):
    not_visited = [[-1]*W for i in range(H)]
    not_visited[i][j] = 0
    stack = deque()
    stack.append((i,j,"#"))

    while stack != deque([]):
        y,x,mark = stack.popleft()
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and mark != S[y+dy[i]][x+dx[i]]  and not_visited[y+dy[i]][x+dx[i]] == -1:
                not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x] + 1
                if mark == "#":
                    stack.append((y+dy[i],x+dx[i],"."))
                else:
                    stack.append((y+dy[i],x+dx[i],"#"))

    odd = 0
    for i in range(H):
        for j in range(W):
            if not_visited[i][j] > 0 and not_visited[i][j] % 2 == 1:
                odd += 1
    
    return odd

ans = 0
if start:
    for sta in start:
        i,j = sta[0],sta[1]
        ans += distance(i,j)
    print(ans)
else:
    print(ans)

### FIXED CODE ###

import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

S = [list(input()) for i in range(H)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

start = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            start.append((i,j))

not_visited = [[-1]*W for i in range(H)]
def distance(i,j):
    not_visited[i][j] = 0
    stack = deque()
    stack.append((i,j,"#"))

    b,w = 1,0

    while stack != deque([]):
        y,x,mark = stack.popleft()
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and mark != S[y+dy[i]][x+dx[i]]  and not_visited[y+dy[i]][x+dx[i]] == -1:
                not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x] + 1
                if mark == "#":
                    stack.append((y+dy[i],x+dx[i],"."))
                    w += 1
                else:
                    stack.append((y+dy[i],x+dx[i],"#"))
                    b += 1
    
    return b*w

ans = 0
for i in range(H):
    for j in range(W):
        if not_visited[i][j] == -1 and S[i][j] == "#":
            ans += distance(i,j)
print(ans)
### BUGGY CODE ###

import copy

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

ans = [0] * N
def loop():
    global a
    ruir = [0] * (N + 1)
    ruil = [0] * (N + 1)
    for i in range(N):
        ruir[i] += 1
        tmp = i + a[i]
        if tmp < N:
           ruir[tmp + 1] -= 1
    for i in range(N):
        ruir[i + 1] += ruir[i]

    for i in reversed(range(N)):
        if a[i] - 0.5 > -1:
            ruil[i - 1] += 1
            tmp = i - a[i]
            if tmp > 0:
                ruil[tmp - 1] -= 1
    for i in reversed(range(N)):
        ruil[i - 1] += ruil[i]
    cnt = 0
    for i in range(N):
        add = ruir[i] + ruil[i]
        if add > N:
            add = N
        if add == N:
            cnt +=1
        ans[i] = add
    if cnt == N:
        print(*ans)
        exit()
    a = copy.deepcopy(ans)

for i in range(K):
    loop()
print(*ans)

### FIXED CODE ###

import copy

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

ans = [0] * N
def loop():
    global a
    ruir = [0] * (N + 1)
    ruil = [0] * (N + 1)
    for i in range(N):
        ruir[i] += 1
        tmp = i + a[i]
        if tmp < N:
           ruir[tmp + 1] -= 1
    for i in range(N):
        ruir[i + 1] += ruir[i]

    for i in reversed(range(N)):
        if a[i] - 0.5 > -1:
            ruil[i - 1] += 1
            tmp = i - a[i]
            if tmp > 0:
                ruil[tmp - 1] -= 1
    for i in reversed(range(N)):
        ruil[i - 1] += ruil[i]
    cnt = 0
    for i in range(N):
        add = ruir[i] + ruil[i]
        if add > N:
            add = N
        if add == N:
            cnt +=1
        ans[i] = add
    if cnt == N:
        print(*ans)
        exit()
    a = copy.deepcopy(ans)

for i in range(K):
    loop()
print(*ans)
### BUGGY CODE ###

from queue import Queue

N, M = [int(n) for n in input().split()]
graph = {n: [] for n in range(1, N+1)}
for m in range(M):
    A, B = [int(n) for n in input().split()]
    graph[A].append(B)
    graph[B].append(A)

starts_ = sorted(graph.keys(), key=lambda x: len(graph[x]))
starts = iter(starts_)

result_path = []
for start in starts:
    q = Queue()
    needs_start = graph[start]
    q.put([start])
    while not q.empty():
        path = q.get()            
        for t in graph[path[-1]]:
            if t in path:
                continue
            if len(set(needs_start + graph[t]) - set(path + [t])) == 0:
                result_path = path + [t]
                q = Queue()
                break
            else:
                if len(path + [t]) < N:
                    q.put(path+[t])
                
    if len(result_path) > 0:
        break
print(len(result_path))
result = ""
for r in result_path:
    result += " {}".format(r)
print(result[1:])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
def inpl(): return map(int, input().split())

N, M = inpl()
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = inpl()
    G[a].append(b)
    G[b].append(a)

searched = [False] * (N+1)

m = 1
searched[m] = True

ans = []
def dfs(c):
    global ans
    searched[c] = True
    for d in G[c]:
        if not searched[d]:
            ans.append(c)
            dfs(d)
            break 
    else:
        ans.append(c)
    
dfs(1)
ans = ans[:0:-1]
dfs(1)

print(len(ans))
print(*ans)
### BUGGY CODE ###

import math

N = int(input())
upper = int(math.sqrt(N))
#print(upper)

for n in range(1,N+1):
    myans = 0
    for x in range(1, upper):
        remain = n - x**2
        if remain >= 1:
            y_upper = int(math.sqrt(remain))
            for y in range(1, y_upper+1):
                remain2 = remain - (y**2 + x*y)
                if remain2 >= 1:
                    z_upper = int(math.sqrt(remain2))
                    for z in range(1, z_upper+1):
                        if  z**2 + y*z + z*x == remain2:
                            myans += 1
    print(myans)

### FIXED CODE ###


N = int(input())
myans = [ 0 for n in range(N+1)]
upper = int(N**(2/3))
#print(upper)
for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            v = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if v < N+1:
                myans[v] += 1
#print(myans)
for a,b in enumerate(myans):
    if a != 0:
        print(b)
### BUGGY CODE ###

[n,k]=list(map(int,input().split()))
ablist=[]
suretu=[]
for i in range(n):
    ab=list(map(int,input().split()))
    suretu+=[ab[0]]*ab[1]
suretu.sort()
print(suretu[k-1])

### FIXED CODE ###

[n,k]=list(map(int,input().split()))
ablist=[]
for i in range(n):
    ablist.append(list(map(int,input().split())))
ablist=sorted(ablist,key=lambda x:x[0])
bwa=[0]
for i in range(n):
    bwa.append(bwa[-1]+ablist[i][1])
ind=1
while True:
    if bwa[ind-1]<k<=bwa[ind]:
        break
    ind+=1
print(ablist[ind-1][0])