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

def main():
    n = int(input())
    xyp = [list(map(int,input().split())) for i in range(n)]

    def caldp(a):
        n = len(a)
        a.sort()
        dp = [[float("INF")]*(n+1) for i in range(n+1)]
        dp[0][0] = 0
        for l in range(n):
            for r in range(l+1,n+1):
                now = float("INF")
                for k in range(l,r):
                    count = 0
                    for i in range(l,r):
                        count += abs(a[i][0]-a[k][0])*a[i][1]

                    now = min(now,count)
                for j in range(n):
                    dp[r][j+1] = min(dp[r][j+1],dp[l][j]+now)

                now = 0
                for i in range(l,r):
                    now += abs(a[i][0])*a[i][1]
                for j in range(n+1):
                    dp[r][j] = min(dp[r][j],dp[l][j]+now)

        res = [float("INF")]*(n+1)
        for i in range(n+1):
            res[i] = dp[-1][i]
        return res

    ans = [float("INF")]*(n+1)

    for s in range(1<<n):
        lx = []
        ly = []
        for i in range(n):
            if s >> i & 1:
                lx.append((xyp[i][0],xyp[i][2]))
            else:
                ly.append((xyp[i][1],xyp[i][2]))
        lx = caldp(lx)
        ly = caldp(ly)
        for i in range(len(lx)):
            for j in range(len(ly)):
                ans[i+j] = min(ans[i+j],lx[i]+ly[j])

    for i in ans:
        print(i)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            xcal[i][j] *= l[j][2]
            ycal[i][j] *= l[j][2]
    ans = [float("INF")]*(n+1)

    for i in range(1<<n):
        count = 0
        for j in range(n):
            if i >> j & 1:
                count += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(n):
                if not (i>>k & 1):
                    cost += min(xcal[j][k],ycal[i-j][k])
                if cost > ans[count]:
                    break
            ans[count] = min(ans[count],cost)
            j -= 1

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n, m = map(int, input().split())
gate = []
answer = 0
for i in range(m):
    gate.append([int(j) for j in input().split()])
for k in range(n):
    id = k + 1
    flg = True
    for l in range(m):
        if id < gate[l][0] or id > gate[l][1]:
            flg = False
            break 
    if flg:
        answer += 1
print(answer)

### FIXED CODE ###

# -*- coding: utf-8 -*-

n, m = map(int, input().split())
l = []
r = []
answer = 0
for i in range(m):
    a, b = map(int, input().split())
    l.append(a)
    r.append(b)
min_ok = max(l)
max_ok = min(r)
answer = max_ok - min_ok + 1
if answer < 0:
    answer = 0
print(answer)
### BUGGY CODE ###

n, k = map(int, input().split())
A = tuple(map(int, input().split()))

d = dict()
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

if len(d) <= k:
    print(0)
else:
    c = 0
    while len(d) > k:
        v = d.pop(min(d, key=d.get))
        c += v
    print(c)

### FIXED CODE ###

n, k = map(int, input().split())
A = tuple(map(int, input().split()))
d = dict()
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

cs = sorted(list(d.values()))

if len(cs) <= k:
    print(0)
else:
    c = 0
    print(sum(cs[:-k]))
### BUGGY CODE ###

import bisect
a,b,q=map(int,input().split())
s=[]
t=[]
x=[]
s.append(-float("inf"))
t.append(-float("inf"))
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(float("inf"))
t.append(float("inf"))
s.sort()
t.sort()
for i in range(q):
    x=int(input())
    ans=float("inf")
    tmp_s_1=bisect.bisect_left(s,x)-1
    tmp_s_2=tmp_s_1+1
    tmp_s_1_t=bisect.bisect_left(t,s[tmp_s_1])
    tmp_s_2_t=bisect.bisect_left(t,s[tmp_s_2])
    ans=min(abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t-1]), abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t-1]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t]))
    tmp_t_1=bisect.bisect_left(t,x)-1
    tmp_t_2=tmp_t_1+1
    tmp_t_1_s=bisect.bisect_left(s,t[tmp_t_1])
    tmp_t_2_s=bisect.bisect_left(s,t[tmp_t_2])
    ans=min(ans, abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s-1]), abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s-1]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s]))
    print(ans)

### FIXED CODE ###

from bisect import bisect_left
a,b,q=map(int,input().split())
s=[]
t=[]
x=[]
s.append(-10**12)
t.append(-10**12)
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(10**12)
t.append(10**12)
for i in range(q):
    x=int(input())
    tmp_s=bisect_left(s,x)-1
    tmp_s_1=s[tmp_s]
    tmp_s_2=s[tmp_s+1]
    tmp_t=bisect_left(t,x)-1
    tmp_t_1=t[tmp_t]
    tmp_t_2=t[tmp_t+1]
    print(min(abs(x-tmp_s_1)+abs(tmp_s_1-tmp_t_1),
    abs(x-tmp_s_1)+abs(tmp_s_1-tmp_t_2),
    abs(x-tmp_s_2)+abs(tmp_s_2-tmp_t_1),
    abs(x-tmp_s_2)+abs(tmp_s_2-tmp_t_2),
    abs(x-tmp_t_1)+abs(tmp_t_1-tmp_s_1),
    abs(x-tmp_t_1)+abs(tmp_t_1-tmp_s_2),
    abs(x-tmp_t_2)+abs(tmp_t_2-tmp_s_1),
    abs(x-tmp_t_2)+abs(tmp_t_2-tmp_s_2)))
### BUGGY CODE ###

def main():
  N, W = map(int, input().split())
  dp = [-1] * (W + 1)
  dp[0] = 0
  ws = []
  ps = []
  for _ in range(N):
    w, v = map(int, input().split())
    ws.append(w)
    ps.append(v)
  for i in range(len(ws)):  
    for j in range(W - ws[i], -1, -1):
      dpi = dp[j]
      if dpi != -1:
        if dp[j + ws[i]] < dpi + ps[i]:
          dp[j + ws[i]] = dpi + ps[i]
  print(max(dp))
main()

### FIXED CODE ###

def dynamicprogramming():
  N, W = map(int, input().split())
  dp = [-1] * (W + 1)
  dp[0] = 0
  for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        dpi = dp[i]
        if dpi != -1:
          if dp[i + w] < dpi + v:
            dp[i + w] = dpi + v
  print(max(dp))

dynamicprogramming()
### BUGGY CODE ###

N,M = map(int, raw_input().split())
MOD = 10**9+7
 
F = [0]*100100
F[0] = 1
for i in range(1,100100):
  F[i] = i*F[i-1]%MOD
 
ans = 1
d = 2
while M>1:
  c = 0
  while M%d==0:
    M /= d
    c += 1
  if c>0:
    ans *= F[N+c-1]
    ans %= MOD
    ans *= pow(F[N-1], MOD-2, MOD)
    ans %= MOD
    ans *= pow(F[c], MOD-2, MOD)
    ans %= MOD
  d += 1

print ans

### FIXED CODE ###

N,M = map(int, raw_input().split())
MOD = 10**9+7

F = [0]*100100
F[0] = 1
for i in range(1,100100):
  F[i] = i*F[i-1]%MOD

ans = 1
d = 2
while M>1:
  c = 0
  while M%d==0:
    M /= d
    c += 1
  if c>0:
    ans *= F[N+c-1]
    ans %= MOD
    ans *= pow(F[N-1], MOD-2, MOD)
    ans %= MOD
    ans *= pow(F[c], MOD-2, MOD)
    ans %= MOD
  d += 1
  if d*d>M:
    d = M

print ans
### BUGGY CODE ###

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

    ans = 1
    for c in 'RGB':
        ans *= s.count(c)

    for j in range(N):
        for i in range(j):
            k = (j - i) + j
            if k >= N: continue
            if len({s[x] for x in (i, j, k)}) == 3:
                ans -= 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from bisect import bisect_left

    N = int(input())
    s = input()

    Rs = []
    Gs = []
    Bs = []
    for i, c in enumerate(s):
        if c == 'R':
            Rs.append(i)
        elif c == 'G':
            Gs.append(i)
        else:
            Bs.append(i)

    s += 'Z' * 4000

    ans = 0
    for mid in Rs:
        for g in Gs:
            if g >= mid: break
            ans += len(Bs) - bisect_left(Bs, mid) - (1 if s[mid * 2 - g] == 'B' else 0)
        for b in Bs:
            if b >= mid: break
            ans += len(Gs) - bisect_left(Gs, mid) - (1 if s[mid * 2 - b] == 'G' else 0)
    for mid in Gs:
        for r in Rs:
            if r >= mid: break
            ans += len(Bs) - bisect_left(Bs, mid) - (1 if s[mid * 2 - r] == 'B' else 0)
        for b in Bs:
            if b >= mid: break
            ans += len(Rs) - bisect_left(Rs, mid) - (1 if s[mid * 2 - b] == 'R' else 0)
    for mid in Bs:
        for r in Rs:
            if r >= mid: break
            ans += len(Gs) - bisect_left(Gs, mid) - (1 if s[mid * 2 - r] == 'G' else 0)
        for g in Gs:
            if g >= mid: break
            ans += len(Rs) - bisect_left(Rs, mid) - (1 if s[mid * 2 - g] == 'R' else 0)
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())
### BUGGY CODE ###

# APC001C - Vacant Seat
def main():
    # if no vacant seat in [0, i)
    # -> seat[0] == seat[i] if i % 2 else seat[0] != seat[i]
    N = int(input())
    print(0)
    seat_zero = input().rstrip()
    if seat_zero == "Vacant":
        return
    left, right = 0, N
    for _ in range(19):
        mid = (left + right) // 2
        print(mid)
        this_seat = input().rstrip()
        if this_seat = "Vacant":
            return
        if mid % 2 == (seat_zero != this_seat):
            left = mid
        else:
            right = mid


if __name__ == "__main__":
    main()

### FIXED CODE ###

# APC001C - Vacant Seat
def main():
    # if no vacant seat in [0, i)
    # -> seat[0] == seat[i] if i % 2 else seat[0] != seat[i]
    N = int(input())
    print(0, flush=1)
    seat_zero = input().rstrip()
    if seat_zero == "Vacant":
        return
    left, right = 0, N
    for _ in range(19):
        mid = (left + right) // 2
        print(mid, flush=1)
        this_seat = input().rstrip()
        if this_seat == "Vacant":
            return
        if mid % 2 == (seat_zero != this_seat):
            left = mid
        else:
            right = mid


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

import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))
L = [0] * Q
R = [0] * Q
for i in range(Q):
    l,r = map(int, input().split())
    L[i] = l
    R[i] = r
D = {}
E = [{0:0}] * N
for i in range(N):
    if D.get(C[i], -1) == -1:
        D[C[i]] = 1
        D_other = dict(D)
        E[i] = D_other
    else:
        D[C[i]] += 1
        D_other = dict(D)
        E[i] = D_other

for i in range(Q):
    if L[i] == 1:
        E_dif = E[R[i] - 1]
    else:
        E_dif = dict(E[R[i] - 1].items() - E[L[i] - 2].items())
    ans = len(E_dif.values())
    print(ans)

### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

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

for i in range(Y//1000+1):
    for j in range(Y//1000+1):
        k = (Y-i*1000-j*5000)//10000
        if 1000*i+j*5000+k*10000 == Y and i+j+k == N and k >= 0:
            print(k,j,i)
            exit()
else:
    print(-1,-1,-1)

### FIXED CODE ###

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

for i in range(N+1):
    for j in range(N+1):
        k = N-i-j
        if 1000*i+j*5000+k*10000 == Y and i+j+k == N and k >= 0:
            print(k,j,i)
            exit()
else:
    print(-1,-1,-1)
### BUGGY CODE ###

N = int(input())
s = list(map(int ,input().split()))
con = 0
for i in range(N):
  for j in range(i + 1 , N):
    if s[i] == j + 1 and s[j] == i + 1:
      con += 1
print(con)

### FIXED CODE ###

N = int(input())
s = list(map(int ,input().split()))
con = 0
for i in range(N):
  if s[s[i] - 1] == i + 1:
    con += 1
print(con // 2)
### BUGGY CODE ###

p,q,r=map(int,input().split())

    
def comb_mod(N,K,modp):

    K_fact=1
    NK_fact=1
    N_fact=1

    for i in range(1,K+1):
        K_fact*=i
    for i in range(1,N-K+1):
        NK_fact*=i
    for i in range(1,N+1):
        N_fact*=i

    K_inv=pow(K_fact, -1, modp)
    NK_inv=pow(NK_fact, -1, modp)
    pat=(N_fact*K_inv)%modp*NK_inv%modp
    return pat

pat=comb_mod(p*q-2,r-2,10**9+7)

ans=0
for i in range(0,q+1):
    ans+=i*(q-i)*p*p

for k in range(0,p+1):
    ans+=k*(p-k)*q*q


print(ans*pat%(10**9+7))

### FIXED CODE ###

p,q,r=map(int,input().split())

    
def comb_mod(N,K,modp):

    K_fact=1
    NK_fact=1
    N_fact=1

    for i in range(1,K+1):
        K_fact*=i
        K_fact=K_fact%modp
    for i in range(1,N-K+1):
        NK_fact*=i
        NK_fact=NK_fact%modp
    for i in range(1,N+1):
        N_fact*=i
        N_fact=N_fact%modp

    K_inv=pow(K_fact, -1, modp)
    NK_inv=pow(NK_fact, -1, modp)
    pat=(N_fact*K_inv)%modp*NK_inv%modp
    return pat

pat=comb_mod(p*q-2,r-2,10**9+7)

ans=0
for i in range(0,q+1):
    ans+=i*(q-i)*p*p
    ans=ans%(10**9+7)
    
for k in range(0,p+1):
    ans+=k*(p-k)*q*q%(10**9+7)
    ans=ans%(10**9+7)

print(ans*pat%(10**9+7))
### BUGGY CODE ###

import numpy as np

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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

            
def judge(x, lst):

    length = len(lst)
    all_pair = (length*(length-1) // 2) + length
    
    lst_r = [-1 if i < x else 1 for i in lst]
    array = np.cumsum(np.array(lst_r))
    lst_accum = array - min(array) + 1
    
    bit = Bit(max(lst_accum))
    ans = 0
    for i, p in enumerate(lst_accum):
        bit.add(p, 1)
        ans += i + 1 - bit.sum(p)
    
    ans = all_pair - ans
    if ans >= (all_pair//2) + 1:
        return True
    else:
        return False

    
lst = sorted(lst)
low = 0
high = len(lst) - 1
t = (low+high) // 2
while low < high:
    i = lst[t]
    if judge(i, lst):
        if low == t:
            break
        low = t
        t = (low+high) // 2
    else:
        high = t
        t = (low+high) // 2
        
print(lst[high]) if judge(lst[high], lst) else print(lst[t])

### FIXED CODE ###

from itertools import accumulate
from math import ceil
 
N = int(input())
A = list(map(int, input().split()))
 
if N == 1:
    print(A[0])
    exit()
 
 
class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)
 
    def reset(self):
        self.bit = [0] * (self.size + 1)
 
 
BIT = BinaryIndexedTree(N)  # Binaryの先頭の分
lo, hi = -1, 10 ** 9 + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2
 
    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]
 
    # 累積和をとる
    Binary = list(accumulate(Binary))
 
    # BITを初期化
    BIT.reset()
 
    # 転倒数っぽいものを数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += BIT.sum(Binary_sorted[b]) + (b >= 0)
        BIT.add(Binary_sorted[b], 1)
 
    if inversion >= ceil((N * (N + 1) / 2) / 2):
        lo = X
    else:
        hi = X
 
print(lo)
### BUGGY CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
S = input()
T = input()

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b


def lcs(s, t):
    dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
    for i in range(len(S)):
        for j in range(len(T)):
            if S[i] == T[j]:
                dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i][j+1])

    ans = ''
    i = len(S)
    j = len(T)
    while (i>0  and j>0):
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans += s[i-1] 
            i -= 1
            j -= 1
    
    print(ans[::-1])

        
lcs(S, T)



### FIXED CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
S = input()
T = input()

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b


def lcs(s, t):
    dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
    for i in range(len(S)):
        for j in range(len(T)):
            if S[i] == T[j]:
                dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i][j+1])

    ans = ''
    i = len(S)
    j = len(T)
    while (i>0  and j>0):
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans += s[i-1] 
            i -= 1
            j -= 1
    
    print(ans[::-1])

        
lcs(S, T)
### BUGGY CODE ###

N = int(input())
S = list(input())
L = ["0","1","2","3","4","5","6","7","8","9"]
cnt = 0
for a in L:
    for b in L:
        for c in L:
            target = [a,b,c]
            T = 0
            for i in range(N):
                see = S[i]
                if target[T]==see:
                    T+=1
                    if T==3:
                        cnt += 1
                        break
print(cnt)

### FIXED CODE ###

N = int(input())
S = list(input())
L = ["0","1","2","3","4","5","6","7","8","9"]
cnt = 0
for a in L:
    for b in L:
        for c in L:
            target = [a,b,c]
            T = 0
            for i in range(N):
                see = S[i]
                if target[T]==see:
                    T+=1
                    if T==3:
                        cnt += 1
                        break
print(cnt)
### BUGGY CODE ###

N,M,V,P=map(int, input().split())
*A,=map(int, input().split())

A.sort()
ans=P
for i in range(N-P):
    Ax = A[-P]  #上位Pの中の最下位
    mine = A[i] + M #自分に全力で投票
    if mine < Ax: continue #逆転不能
    votes = M*V
    votes -= M #自分への票
    votes -= min(P-1, V) * M #上位陣のx以外に全力で投票
    votes -= sum([min(mine - A[j], M) for j in range(N-P+1) if i!=j]) #逆転されない程度に下位陣に投票
    if votes > 0 : continue #再逆転される
    ans += 1
print(ans)

### FIXED CODE ###

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

A.sort(reverse=True)
p = A[P-1]

#X番目の問題に可能性があるかどうか(0-indexed)
def f(X):
    x = A[X]
    if x + M < p: return False
    votes = M*V
    votes -= M * (P-1)
    for i in range(P-1,N):
        votes -= min(M, x + M - A[i])
    return votes <= 0

ok = 0
over = N
while over - ok > 1:
    mid = (over + ok) // 2
    if f(mid): ok = mid
    else: over = mid
print(ok+1)
### BUGGY CODE ###

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

flg = 1
prev = 0
A = []
for i in range(N):
    if A_raw[i] <= prev:
        flg = 0
    prev = A_raw[i]
    if A_raw[i] > 1000:
        A.append(1000)
    else:
        A.append(A_raw[i])

if flg:
    print(1)
    exit()

ok = N
ng = 0
mid = (ok + ng) // 2
while ok - ng > 1:
    ng_flg = 0
    word = [1] * A[0]
    for i in range(1, N):
        if A[i] > A[i-1]:
            word.extend([1] * (A[i] - A[i-1]))
        else:
            word_prev = word[:A[i]]
            k = A[i] - 1
            while True:
                if k == -1:
                    ng_flg = 1
                    break
                if word_prev[k] != mid:
                    word_prev[k] += 1
                    word = word_prev
                    break
                else:
                    word_prev[k] = 1
                    k -= 1
        if ng_flg == 1:
            break
    if not ng_flg:
        ok = mid
    else:
        ng = mid
    mid = (ok + ng) // 2

print(ok)


### FIXED CODE ###

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

flg = 1
prev = 0
A = []
for i in range(N):
    if A_raw[i] <= prev:
        flg = 0
    prev = A_raw[i]
    if A_raw[i] <= 50:
        A.append(A_raw[i])

if flg:
    print(1)
    exit()

N = len(A)
if N <= 1:
    print(2)
    exit()

ok = N
ng = 1
mid = (ok + ng) // 2
while ok - ng > 1:
    ng_flg = 0
    word = [1] * A[0]
    for i in range(1, N):
        if A[i] > A[i-1]:
            word.extend([1] * (A[i] - A[i-1]))
        else:
            word_prev = word[:A[i]]
            k = A[i] - 1
            while True:
                if k == -1:
                    ng_flg = 1
                    break
                if word_prev[k] != mid:
                    word_prev[k] += 1
                    word = word_prev
                    break
                else:
                    word_prev[k] = 1
                    k -= 1
        if ng_flg == 1:
            break
    if not ng_flg:
        ok = mid
    else:
        ng = mid
    mid = (ok + ng) // 2

print(ok)
### BUGGY CODE ###

n, k = map(int, input().split())
H = list(map(int, input().split()))
dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[i - j - 1] + abs(H[i] - H[i - j - 1]) for j in range(min(k, i)))

print(dp[n - 1])


### FIXED CODE ###

n, k = map(int, input().split())
H = list(map(int, input().split()))
dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[i - j - 1] + abs(H[i] - H[i - j - 1]) for j in range(min(k, i)))

print(dp[n - 1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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

from collections import defaultdict


N,K = two_int()

dicts = defaultdict(int)
count = 0
for i in range(N):
    a,b = two_int()
    temp = 0
    
    for k,v in dicts.items():
        if k>a:
            dicts[k] += b
        if temp <= k <= a:
            temp = k
            
    dicts[a] = b+dicts[temp]

output = [ [k,v] for k,v in dicts.items()]

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

ans=0
for i in range(len(temp)-1):
    if temp[i][1] < K <= temp[i+1][1]:
        ans=temp[i+1][0]

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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

from collections import defaultdict


N,K = two_int()


query = []
for i in range(N):
    query.append(two_int() )

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

ans=0
sums=0
for q in query:
    if sums < K <= sums+q[1]:
        ans=q[0]
        break
    
    sums += q[1]

print(ans)