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

n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = next
    return start

stack = [s]
ifReached[s-1] = True
count = 0
unreachable = False
while True:
    n_stack = list(set(indicate3(stack,path)))
    tmp_stack = []
    for position in n_stack:
        if ifReached[position-1] == False:
            tmp_stack.append(position)
            ifReached[position-1] = True


    if len(tmp_stack) == 0:
        print(-1)
        break

    if g in n_stack:
        count += 1
        print(count)
        break
    else:
        if n_stack == stack:
            print(-1)
            break
        else:
            count += 1
            if unreachable == True:
                print(-1)
                break
    stack = tmp_stack

### FIXED CODE ###

n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = list(set(next))
    return start

stack = [s]
ifReached[s-1] = True
count = 0
while True:
    n_stack = list(set(indicate3(stack,path)))

    tmp_stack = []
    for position in n_stack:
        if ifReached[position-1] == False:
            tmp_stack.append(position)
            ifReached[position-1] = True

    if len(tmp_stack) == 0:
        print(-1)
        break

    count += 1
    if g in tmp_stack:
        print(count)
        break
    stack = tmp_stack
### BUGGY CODE ###

def rev_f(string , i):
    if i[2] == '2':
        string = string + i[4]

    if i[2] == '1':
        string = i[4] + string
    return string



def rev_s(string , i):
    if i[2] == '1':
        string = string + i[4]

    if i[2] == '2':
        string = i[4] + string
    return string




string = input()
num = int(input())
q_list = []
reverse_num = 0
reverse = True
reverese_s = False
for a in range(num):
    i = input()
    if i == '1':
        reverse_num  +=1 
        if reverese_s:
            reverese_s = False
        else:
            reverese_s = True
    else:
        if reverese_s == False:
            string = rev_f(string,i)

        if reverese_s ==True:
            string = rev_s(string,i)
        
if reverse_num %2 == 0:
    reverse = False
    
if reverse == True:
    string = string[::-1]
print(string)


### FIXED CODE ###

def rev_f(string , i):
    if i[2] == '2':
        string = string + i[4]

    if i[2] == '1':
        string = i[4] + string
    return string



def rev_s(string , i):
    if i[2] == '1':
        string = string + i[4]

    if i[2] == '2':
        string = i[4] + string
    return string



front = ''
back = ''
string = input()
num = int(input())
q_list = []
reverse_num = 0
reverse = True
reverese_s = False
for a in range(num):
    i = input()
    if i == '1':
        reverse_num  +=1 
        if reverese_s:
            reverese_s = False
        else:
            reverese_s = True
    else:
        if reverese_s == False:
            if i[2] == '2':
                back += i[4]
            else:
                front = i[4] + front
            
        else :
            if i[2] == '2':
                front = i[4] + front
            else:
                back += i[4]
        
if reverse_num %2 == 0:
    reverse = False
    
string = front + string + back
if reverse == True:
    string = string[::-1]
    
print(string)
### BUGGY CODE ###

n, m = map(int, input().split())
l = list(map(int, input().split()))

s = [0]
for i in range(n):
    s.append(sum(l[:i+1]))

s = [j%m for j in s]
s.sort()

ans = 0
while s:
    cnt = s.count(s[0])
    s = [x for x in s if x != s[0]]
    ans += cnt*(cnt-1)//2

print(ans)

### FIXED CODE ###

from collections import Counter

n, m = map(int, input().split())
l = list(map(int, input().split()))

s = [0]
for i in range(n):
    s.append((s[-1]+l[i])%m)

c = Counter(s)

ans = 0
for x in c.values():
    ans += x*(x-1)//2

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

N, K = list(map(int, input().strip().split(" ")))
candles = input().strip()
min_cost_index = candles.count("-")
candles = list(map(int, candles.split(" ")))

def update():
    start_index = max(0, min_cost_index - K - 1)
    end_index = min(N, min_cost_index + K + 1)
    new_candles = candles[start_index: end_index]
    return new_candles

def compute_cost(point_candles):
    if(point_candles[0] * point_candles[-1] >= 0):
        return max(abs(point_candles[0]), abs(point_candles[-1]))
    else:
        return point_candles[-1] - point_candles[0] + min(abs(point_candles[0]), abs(point_candles[-1])) 

candles = update()

N = len(candles)
min_cost = None
patterns = N - K + 1


for start_index in range(patterns):
    cost = compute_cost(candles[start_index:start_index + K])
    if(min_cost == None or min_cost > cost):
        min_cost = cost
print(min_cost)

### FIXED CODE ###

N, K = list(map(int, input().strip().split(" ")))
candles = input().strip()
min_cost_index = candles.count("-")
candles = list(map(int, candles.split(" ")))

def update():
    start_index = max(0, min_cost_index - K - 1)
    end_index = min(N, min_cost_index + K + 1)
    new_candles = candles[start_index: end_index]
    return new_candles

def compute_cost(start_index):
    start_point = candles[start_index]
    end_point = candles[start_index + K - 1]
    if(start_point * end_point >= 0):
        return max(abs(start_point), abs(end_point))
    else:
        return end_point - start_point + min(-start_point, end_point) 

candles = update()

N = len(candles)
min_cost = compute_cost(0)
patterns = N - K + 1

for start_index in range(patterns):
    cost = compute_cost(start_index)
    if(min_cost > cost):
        min_cost = cost
print(min_cost)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1, n//2+1):
    ans += n+1
ans -= n
if n%2 == 1:
    ans += n//2 + 1
print(ans)


### FIXED CODE ###

n = int(input())
ans = (n+1) * (n//2) - n
if n%2 == 1:
    ans += n//2 + 1
print(ans)
### BUGGY CODE ###

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

A = [0]+A
B = [0]+B
for i in range(1, N+1):
    A[i] += A[i-1]
for i in range(1, M+1):
    B[i] += B[i-1]
ans = 0
best = M
for i in range(N+1):
    if A[i] > K:
        break
    for j in range(best, -1, -1):
        if A[i] + B[j] <= K:
            ans = max(ans, i+j)
            break
print(ans)


### FIXED CODE ###

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

a = [0]
b = [0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i] +B[i])
ans = 0
j = M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K -a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

N=int(input())
num=0
l=[]
for h in range(N):
    s=input()
    if s not in l:
        l.append(s)
print(len(l))


### FIXED CODE ###

N=int(input())
S=[input() for _ in range(N)]
print(len(set(S)))
### BUGGY CODE ###

n,w = map(int, input().split())
wv = []
for _ in range(n):
    data = list(map(int,input().split()))
    wv.append(data)

dct={}

def solve(i,j):
    if i>=n:
        return 0

    ky = str(i)+"_"+str(j)
    if ky in dct:
        return dct[ky]


    weight=wv[i][0]
    value =wv[i][1]

    if j<weight: # can't push this item
        val = solve(i+1,j)
    else:# push or not push
        val =  max(solve(i+1,j-weight)+value, solve(i+1,j))

    dct[ky] = val

    return val

print(solve(0,w))

### FIXED CODE ###

n,w = map(int, input().split())
wv = []
for _ in range(n):
    data = list(map(int,input().split()))
    wv.append(data)

dp = [[0 for i in range(w+1)] for j in range(n+1)]

for item in range(n):
    now_w=wv[item][0]
    now_v=wv[item][1]

    for weight in range(w+1):
        ans1=dp[item][weight]
        ans2=-1
        if weight - now_w >= 0:
            ans2=dp[item][weight-now_w]+now_v
        dp[item+1][weight] = max(ans1,ans2)

print(dp[n][w])
### BUGGY CODE ###

word = input()
for i in range(len(word)):
  if (word[i] == '?'):
    if ((word[i-1] == 'P') or (i == len(word)-1)):
    	word = word[:i] + 'D' + word[i+1:]
    elif ((i != len(word) -1) and ((word[i+1] == "D") or word[i+1] == "?")):
    	word = word[:i] + 'P' + word[i + 1:]
    else:
    	word = word[:i] + 'D' + word[i+1:]
print(word)

### FIXED CODE ###

word = input()
start = 0
end = len(word)
while(True):
	i = word.find('?', start, end)
	if (i == -1):
		break
	elif (i == (end-1)):
		word = word.replace('?', "D", 1)   
	elif (word[i-1] == 'P'):
		word = word.replace('?', "D", 1)
	elif ((word[i+1] == "?") or (word[i+1] == "D")):
		word = word.replace('?', "P", 1)
	else:
		word = word.replace('?', "D", 1)
	start = i + 1
print(word)
### BUGGY CODE ###

ans = 0
k = int(input())
def f(x,y):
  x,y= min(x,y),max(x,y)
  while y%x != 0:
    z = y%x
    y = x
    x = z
  else:
    return x
def ff(a,b,c):
  return f(c,f(a,b))
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            c = sorted([i,j,k])
            ans += ff(c[0],c[1],c[2])
print(ans)

### FIXED CODE ###

ans = 0
k = int(input())
def f(x,y):
  x,y= min(x,y),max(x,y)
  while y%x != 0:
    z = y%x
    y = x
    x = z
  else:
    return x
def ff(a,b,c):
  return f(c,f(a,b))
for i in range(1,k+1):
    for j in range(i,k+1):
        for k in range(j,k+1):
            if i == j == k:
              ans += ff(i,j,k)
            elif (i == j) or (j == k):
                ans += 3*ff(i,j,k)
            else:
                ans += 6*ff(i,j,k)            
print(ans)
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
ans = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      ans += gcd(a,b,c)
print(ans)

### FIXED CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
ans = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      ans += gcd(a,b,c)
print(ans)
### BUGGY CODE ###

A, B = map(int, input().split())

S = A if A < B else B

s = int(S**(1/2))+1

cd = [1]
if (A % 2 == 0) and (B % 2 == 0):
    cd.append(2)

for i in range(3, S, 2):
    if A % i == 0:
        if B % i == 0:
            cd.append(i)
            
#print(cd)

count = 0
for i in cd:
    for c in range(2, int(i**(1/2))+1):
        if i % c == 0:
            break
    else:
        count += 1
         
print(count)

### FIXED CODE ###

A, B = map(int, input().split())

import math

a = math.floor(math.sqrt(A))
b = math.floor(math.sqrt(B))

A_ = [1]
i = 2
while i <= a:
    if A % i == 0:
        A //= i
        A_.append(i)
    else:
        i += 1
A_.append(A)
        
B_ = [1]
i = 2
while i <= b:
    if B % i == 0:
        B //= i
        B_.append(i)
    else:
        i += 1
B_.append(B)

#print(A_)
#print(B_)
#print(set(A_))
#print(set(B_))

count = 0
for i in set(A_):
    if i in set(B_):
        count += 1

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

import numpy as np
N, K = map(int, input().split())
H = [int(h) for h in input().split()]
H = np.array(H)

dp = np.array([0]*(N+1))
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    if n < K:
        dp[n] = np.amin(dp[np.maximum(n-k, 0)] + np.abs(H[n]-H[np.maximum(n-k, 0)]))
    else:
        dp[n] = np.amin(dp[n - k] + np.abs(H[n] - H[n - k]))


print(dp[N-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
# H = np.array([int(h) for h in input().split()])
H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    start = max(n-K, 0)
    #if n < K:
    #   dp[n] = np.amin(dp[start] + np.abs(H[n]-H[start]))
    #else:
    #   dp[n] = np.min(dp[n - k] + np.abs(H[n] - H[n - k]))
    dp[n] = np.min(dp[start:n] + np.abs(H[n]-H[start:n]))

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

n=int(input())
a=list(map(int,input().split()))
v=sum(a)
ans=[]
for i in range(1,n):
    x=sum(a[0:i])
    y=v-x
    ans.append(abs(y-x))
print(min(ans))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
v=sum(a)
x=sum(a)
ans=[]
for i in range(n-1):
    x=x-a[i]
    ans.append(abs(v-2*x))
print(min(ans))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
ans = 0
for i in range(len(A)-1):
    #print(A[i+1:])
    ans += (A[i] * sum(A[i+1:]))
print(ans % mod)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
ans = 0
X = sum(A)
for i in range(len(A)-1):
    Y = A[i]
    X -= Y
    ans += (Y * X)
print(ans % mod)
### BUGGY CODE ###

N = int(input())
A = list(input().split())
for i in range(N):
    A[i] = int(A[i])
sum = 1

for i in range(N):
    sum = sum * A[i]

if sum <= 10**18:
    print(sum)
else:
    print(-1)
    

### FIXED CODE ###

N = int(input())
A = list(input().split())
flag = 0
for i in range(N):
    A[i] = int(A[i])
    if A[i] == 0:
        flag = -1
sum = 1

for i in range(N):
    if sum <= 10**18:
        sum = sum * A[i]
    else:
        break


if sum <= 10**18:
    print(sum)
else:
    if flag == -1:
        print(0)
    else:
        print(-1)
### BUGGY CODE ###

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

if 1 in a:
  dp[1]=0
else:
  dp[1]=1

for i in range(1,n):
  if i+1 not in a:
    
    dp[i+1]=(dp[i]+dp[i-1])
    dp[i+1]%=(10**9+7)
  else:
    continue
    
print(dp[n])


### FIXED CODE ###

N,M = map(int,input().split())
a = set(int(input()) for x in range(M))
A = [0]*(N+1)
mod = 1000000007
A[0] = 1
if not(1 in a):
  A[1] = 1
for i in range(2,N+1):
    if i in a:
      A[i] = 0
    else:
      A[i] = (A[i-2] + A[i-1]) % mod
print(A[N])
### BUGGY CODE ###

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

dp = [10**9]*N
dp[0] = 0

for i in range(1,N):
  for j in range(K+1):
    if i-j >= 0:
      dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
  
print(dp[N-1])

### FIXED CODE ###

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

dp = [10**9]*N
dp[0] = 0

for i in range(1,N):
  for j in range(K+1):
    if i-j >= 0:
      dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
  
print(dp[N-1])
### BUGGY CODE ###

n,*a=map(int,open(0))
for i in range(n):
    x=a[i]
    a[i]=0
    print(max(a))
    a[i]=x

### FIXED CODE ###

n,*a=map(int,open(0))
b=sorted(a)
for i in range(n):
    if a[i]==b[-1]:
        print(b[-2])
    else:
        print(b[-1])
### BUGGY CODE ###

import random, math
random.seed()
def gen(a, b, num):
    result = set()
    while 1:
        while 1:
            v = random.randint(a, b)//2*2+1
            if v not in result:
                break
        for x in range(3, int(math.sqrt(v))+1, 2):
            if v % x == 0:
                break
        else:
            result.add(v)
            if len(result) == num:
                break
    return result
class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod
        self.rev = pow(base, mod-2, mod)

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            num = ord(s[i])
            tmp = (tmp*base + num) % mod
            h[i+1] = tmp
    def calc(self, l, r):
        return (self.h[r] - self.h[l] * pow(self.base, r-l, self.mod)) % self.mod
    def fixed(self, length):
        v = pow(self.base, length, self.mod)
        h = self.h; mod = self.mod
        def fixed_calc(l):
            return (h[length+l] - h[l] * v) % mod
        return fixed_calc
class RRH():
    def __init__(self, s, num=10, primes=None):
        primes = primes or gen(2, 10**3, num)
        MOD = 10**9+7
        self.rhs = [RH(s, p, MOD) for p in primes]
    def calc(self, l, r):
        return [rh.calc(l, r) for rh in self.rhs]
    def fixed(self, length):
        fs = [rh.fixed(length) for rh in self.rhs]
        def multi_fixed_calc(l):
            return list(f(l) for f in fs)
        return multi_fixed_calc

T = input(); P = input()
primes = gen(2, 10**3, 3)
HT = RRH(T, primes=primes)
HP = RRH(P, primes=primes)

pv = HP.calc(0, len(P))
calc = HT.fixed(len(P))
for i in range(len(T)-len(P)+1):
    if calc(i) == pv:
        print(i)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
write = sys.stdout.write

class KMP:
    def __init__(self, W):
        L = len(W)
        T = [0] * (L+1)
        T[0] = -1
        c = 0
        for p in range(1, L):
            if W[p] == W[c]:
                T[p] = T[c]
            else:
                T[p] = c
                c = T[c]
                while c >= 0 and W[p] != W[c]:
                    c = T[c]
            c += 1
        T[L] = c
        self.T = T
        self.W = W

    def search(self, S):
        W = self.W; T = self.T
        R = []
        LS = len(S); LW = len(W)
        # S[i], W[j]
        i = j = 0
        while i < LS:
            if S[i] == W[j]:
                i += 1; j += 1
                if j == LW:
                    R.append(i-j)
                    j = T[j]
            else:
                j = T[j]
                if j < 0:
                    i += 1
                    j += 1
        return R

def solve():
    T = readline().strip()
    P = readline().strip()
    kmp = KMP(P)
    res = kmp.search(T)
    for p in res:
        write("%d\n" % p)
solve()
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

questions = []
for i in range(q):
    questions.append(list(map(int, input().split())))

ac_positions = []
for i in range(n):
    if s[i:i + 2] == 'AC':
        ac_positions.append(i + 1)
pass

for question in questions:
    ac_count = 0

    for ac_position in ac_positions:
        if question[0] <= ac_position and ac_position + 1 <= question[1]:
            ac_count += 1

    print(ac_count)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
questions = [list(map(int, input().split())) for _ in range(q)]

ac_sum = [0]
for i in range(1, n + 1):
    ac_sum.append(ac_sum[i-1] + 1 if s[i-1 : i+1] == 'AC' else ac_sum[i-1])

for l, r in questions:
    print(ac_sum[r-1] - ac_sum[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)


N, M = map(int, input().split())
G = [[] for _ in [0]*N]
for _ in [0]*(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

add = [0]*N
for _ in [0]*M:
    p, x = map(int, input().split())
    p -= 1
    add[p] += x
counter = [0]*N

def dfs(v, p, x):
    counter[v] = x
    for u in G[v]:
        if u == p:
            continue
        dfs(u, v, x+add[u])


dfs(0, -1, add[0])

print(*counter)


### FIXED CODE ###

# AtCoder Beginner Contest 138
# D - Ki
# https://atcoder.jp/contests/abc138/tasks/abc138_d
import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.readline
N, Q = map(int, input().split())

G = [[] for _ in [0]*N]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

counter = [0]*N

for _ in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

visited = [False]*N


def dfs(v=0, x=0):
    visited[v] = True
    counter[v] += x
    for u in G[v]:
        if visited[u]:
            continue
        dfs(u, counter[v])


dfs()
print(*counter)
### BUGGY CODE ###

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

    password = set()

    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            for k in range(10):
                if str(k) in S[j + 1:]:
                    password.add(S[i] + S[j] + str(k))

    print(len(password))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ans = 0
    # password = set()

    # for i in range(N - 2):
    #     for j in range(i + 1, N - 1):
    #         for k in range(10):
    #             if str(k) in S[j + 1:]:
    #                 password.add(S[i] + S[j] + str(k))

    for i in range(10):
        for j in range(10):
            for k in range(10):
                i_index = S.find(str(i))
                j_index = S.find(str(j), i_index + 1)
                k_index = S.find(str(k), j_index + 1)
                if i_index != -1 and j_index != -1 and k_index != -1:
                    ans += 1

    print(ans)


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

def gcd(p,q):
  if p % q == 0:
    return q
  return gcd(q, p%q)


k = int(input())
ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
        ans += gcd(gcd(a,b),c)
print(ans)



### FIXED CODE ###

from math import gcd

k = int(input())
ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    x = gcd(a,b)
    for c in range(1,k+1):
        ans += gcd(x,c)
print(ans)
### BUGGY CODE ###

S = list(input())
a = 0
while True:
    if "0" in S and "1" in S:
        S.pop(S.index("0"))
        S.pop(S.index("1"))
        a += 2
    else:
        break
print(a)

### FIXED CODE ###

S = list(input())
a = S.count("0")
b = S.count("1")
if a == b:
    print(a * 2)
elif a > b:
    print(b * 2)
elif a < b:
    print(a * 2)
### BUGGY CODE ###

N = int(input())
se = [()] * N
for i in range(N):
	x, l = map(int, input().split())
	se[i] = (x-l, x+l)
se = sorted(se, key=lambda x: x[1])
ans = []
while se:
	now = se.pop(0)
	temp = []
	for i, s in enumerate(se):
		if now[1] <= s[0]:
			temp = se[i:]
			break
	se = temp
	ans.append(now)
print(len(ans))

### FIXED CODE ###

N = int(input())
se = [[]] * N
for i in range(N):
	x, l = map(int, input().split())
	se[i] = [x-l, x+l]
se = sorted(se, key=lambda x: x[1])
ans = N
for i in range(1, N):
	if se[i-1][1] > se[i][0]:
		se[i][1] = se[i-1][1]
		ans -= 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N, K = zz()
A, B = [0]*N, [0]*N
lis = []
for i in range(N):
    a, b = zz()
    lis.extend([a]*b)
lis = sorted(lis)
print(lis[K-1])


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

sys.setrecursionlimit(10**6)


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N, K = zz()
A, B = [0]*N, [0]*N
# 力技はだめ
for i in range(N):
    A[i], B[i] = zz()
A, B = zip(*sorted(zip(A, B)))
all_num = 0
for i, b in enumerate(B):
    all_num += b
    if (all_num >= K):
        print(A[i])
        exit()