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

import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense
A = np.array(A)
G = csgraph_from_dense(A, null_value=0)
w = floyd_warshall(G)

for i in range(N):
  for j in range(N):
    if A[i][j] > w[i][j]:
      print(-1)
      exit(0)

ans = 0
for a in A:
  ans += sum(a)
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] == A[i][j]:
        ans -= A[i][j]
        
print(ans // 2)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

import copy
newA = copy.deepcopy(A)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit(0)
      elif A[i][k] + A[k][j] == A[i][j]:
        # A[i][j]の道路は不要
        newA[i][j] = 0

ans = 0
for a in newA:
  ans += sum(a)
print(ans // 2)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)
    result = 0
    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M
            affords -= M * P
            if affords <= 0:
                result += 1
                continue
            break_flag = False

            tmp = sum([min(A[n] + M -A[p], M) for p in range(P, N) if p != n])
            affords -= tmp
            if affords <= 0:
                result += 1
            """
            for p in range(P, N):
                if p == n:
                    continue
                else:
                    affords -= min(A[n] + M - A[p], M)
                    if affords<=0:
                        result += 1
                        break
            """
    print(result)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)

    result = 0

    cumsum = [0 for i in range(N+1)]
    for n in range(N-1):
        cumsum[n+1] = A[n] + cumsum[n]

    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M - M * (P-1)
            if affords <= 0:
                result += 1
                continue
            
            sunmmation = A[n] * (n-P) + M * (n-P) - (cumsum[n] - cumsum[P])
            affords -= sunmmation
            affords -= (N-n) * M

            if affords <= 0:
                result += 1
                continue
    print(result)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)

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

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

cnt = 0
for i in range(n):
    for j in range(i):
        if p[j]<p[i]:
            break
    else:
        cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = 1
tmp_min = p[0]
for i in range(1, n):
    tmp_min = min(tmp_min, p[i]) 
    if tmp_min == p[i]:
        cnt += 1
print(cnt)
### BUGGY CODE ###

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

sumA = [A[N-1]]
for i in range(1, N - 1):
    sumA.insert(0, sumA[0]+A[N-i-1])

ans = 0
for i in range(N-1):
    ans += A[i] * sumA[i]

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


### FIXED CODE ###

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

X = 0
Ans = 0

for i in range(N - 1):
    X += A[i]
    Ans += X * A[i + 1]
    Ans = Ans % (10 ** 9 + 7)

print(Ans)
### BUGGY CODE ###

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

half=[]
for i in range(N):
  half.append(abs(sum(A[:i])-sum(A[i:])))
print(min(half))

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

acum = np.cumsum(A)

print(int(min(abs(acum-(sum(A)/2)))*2))
### BUGGY CODE ###

import bisect


n = int(input())
lines = []
for _ in range(n):
    a = int(input())

    index = bisect.bisect_left(lines, a)
    if index == 0:
        lines.insert(0, a)
        continue
    
    lines[index - 1] = a

print(len(lines))


### FIXED CODE ###

import bisect
from collections import deque


n = int(input())
lines = deque()
for _ in range(n):
    a = int(input())

    index = bisect.bisect_left(lines, a)
    if index == 0:
        lines.appendleft(a)
        continue
    
    lines[index - 1] = a

print(len(lines))
### BUGGY CODE ###

n,k,q = map(int,input().split())
Ans = []
for i in range(q):
	Ans.append(int(input()))
for j in range(n):
	if k - q + Ans.count(j+1) > 0:
		print("Yes")
	else:
		print("No")

### FIXED CODE ###

n,k,q = map(int,input().split())
points = []
for i in range(n):
	points.append(k-q)
for i in range(q):
	points[int(input())-1]+=1
for i in range(n):
	if points[i]>0:
		print("Yes")
	else:
		print("No")
### BUGGY CODE ###

N, M, Q = map(int, input().strip().split())
train_starts = {}
for n in range(1, N + 1):
  train_starts[n] = []

for _ in range(M):
  L, R = map(int, input().strip().split())
  train_starts[L].append(R)

for _ in range(Q):
  p, q = map(int, input().strip().split())
  num_trains = 0
  for _p in range(p, N + 1):
    if _p not in train_starts or _p > q:
      continue
    else:
      num_trains += len([_q for _q in train_starts[_p] if _q <=q])
  print(num_trains)

### FIXED CODE ###

n, m, q = map(int, input().split())
trnum = [[0 for _ in range(n+1)] for _ in range(n+1)]
cnum = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
  l, r = map(int, input().split())
  trnum[l][r] += 1

for i in range(1, n+1):
  for j in range(1, n+1):
    trnum[i][j] += trnum[i][j-1]

for i in range(1, n+1):
  for j in range(1, n+1):
    trnum[i][j] += trnum[i-1][j]


for _ in range(q):
  l, r = map(int, input().split())
  print(trnum[r][r] + trnum[l-1][l-1] - trnum[l-1][r] - trnum[r][l-1])
### BUGGY CODE ###

import sys
n, m = map(int, sys.stdin.readline().split())
req = [ list(sorted(map(int, sys.stdin.readline().split())))
        for _ in range(m) ]
req.sort(reverse=True)
c = 0
while req:
    i = req[0][0]
    c += 1
    newreq = []
    for r in req:
        if r[1] <= i:
            newreq.append(r)
    req = newreq
print(c)

### FIXED CODE ###

import sys
n, m = map(int, sys.stdin.readline().split())
req = [ list(sorted(map(int, sys.stdin.readline().split())))
        for _ in range(m) ]
req.sort(reverse=True)
lastcut = None
c = 0
for a, b in req:
    if lastcut is None or a > lastcut or lastcut >= b:
        lastcut = a
        c += 1
print(c)
### BUGGY CODE ###

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

import sys
import os


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

# query
q = int(input())
M = list(map(int, input().split()))

def solve(i, m):
    #print('i', i, 'm', m)

    # i????????\???????????????????????£???m??????????????¨???true
    # i = 0, ..., n-1
    if m == 0:
        return True
    elif i >= n:
        return False
    else:
        # Devide and Conquer

        # i??????????????°??????
        res0 = solve(i + 1, m)
        # i??????????????¶
        res1 = solve(i + 1, m - A[i])

        if res0 or res1:
            return True
        else:
            return False


# main
for m in M:
    result = solve(0, m)
    if result:
        print('yes')
    else:
        print('no')

### FIXED CODE ###

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

import sys
import os


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

# query
q = int(input())
M = list(map(int, input().split()))

# i x m matrix
memo = [[None for i in range(2000)] for j in range(n + 1)]

def solve(i, m):
    if memo[i][m] is not None:
        return memo[i][m]
    #print('i', i, 'm', m)

    # i????????\???????????????????????£???m??????????????¨???true
    # i = 0, ..., n-1
    if m == 0:
        return True
    elif i >= n:
        return False
    else:
        # Devide and Conquer

        # i??????????????°??????
        res0 = solve(i + 1, m)
        # i??????????????¶
        res1 = solve(i + 1, m - A[i])

        if res0 or res1:
            memo[i][m] = True
            return True
        else:
            memo[i][m] = False
            return False


# main
for m in M:
    result = solve(0, m)
    if result:
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 10**18
for i in range(N):
    ans = min(ans, abs(sum(A[:i])-sum(A[i:])))
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 10**18
left = 0
right = sum(A)
for i in range(N):
    ans = min(ans, abs(left-right))
    left += A[i]
    right -= A[i]
print(ans)
### BUGGY CODE ###

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

import queue

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

     r_list = []
     g_list = []
     b_list = []

     ans = 0

     for i in range(n):
          if s[i] == 'R':
               r_list.append(i)
          elif s[i] == 'G':
               g_list.append(i)
          else:
               b_list.append(i)

     for i in range(n):
          if s[i] == 'R':
               spot = r_list.pop(0)
               ans += check(spot, g_list, b_list)

          if s[i] == 'G':
               spot = g_list.pop(0)
               ans += check(spot, r_list, b_list)

          if s[i] == 'B':
               spot = b_list.pop(0)
               ans += check(spot, r_list, g_list)

     print(ans)

def check(spot, first, second):
     ret = 0
     for f in first:
          ignore = f + (f - spot)
          limit_second = [s for s in second if s > f]

          ret += len(limit_second)
          if ignore in limit_second:
               ret += -1

     for s in second:
          ignore = s + (s - spot)
          limit_first = [f for f in first if f > s]

          ret += len(limit_first)
          if ignore in limit_first:
               ret += -1
     
     return ret

if __name__ == "__main__":
    main()


### FIXED CODE ###

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

import queue

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

     r_list = []
     g_list = []
     b_list = []

     ans = 0

     for i in range(n):
          if s[i] == 'R':
               r_list.append(i)
          elif s[i] == 'G':
               g_list.append(i)
          else:
               b_list.append(i)

     for i in range(n):
          if s[i] == 'R':
               ans += check(i, g_list, b_list)

          if s[i] == 'G':
               ans += check(i, r_list, b_list)

          if s[i] == 'B':
               ans += check(i, r_list, g_list)

     print(ans)

def check(spot, first, second):
     ret = 0
     small_first = []
     big_first = []
     small_second = []
     big_second = []

     for f in first:
          if f < spot: small_first.append(spot - f)
          else: big_first.append(f - spot)

     for s in second:
          if s < spot: small_second.append(spot - s)
          else: big_second.append(s - spot)

     return len(small_first) * len(big_second) + len(small_second) * len(big_first) - len(set(small_first) & set(big_second)) - len(set(small_second) & set(big_first))
     
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def a(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return a(n - 1) + a(n - 2)
print(a(int(input())))

### FIXED CODE ###

n = int(input())
la = 1
lla = 2
for i in range(2, n + 1):
    lla, la = la, lla + la
print(la)
### BUGGY CODE ###

N,T = [int(x) for x in raw_input('').split()]
A = [int(x) for x in raw_input('').split()]
max = 0
for i in range(0,len(A)):
  for j in range(i+1,len(A)):
      pf_t = A[j] - A[i]
      if pf_t > max:
        max = pf_t
        spot = [(i,j)]
      elif pf_t == max:
        spot.append((i,j))
print len(spot)

### FIXED CODE ###

raw_input('').split()
A = [int(x) for x in raw_input('').split()]
max = 0
count = 0
pl = 0
msp = A[0]
for i in range(1,len(A)):
  pl_t = pl + A[i] - A[i-1]
  if pl_t <= 0:
    pl = 0
  else:
    pl = pl_t
    if max < pl_t:
      max = pl_t
      count = 1
    elif max == pl_t:
      count += 1
print count
### BUGGY CODE ###

H,W=map(int,input().split())
grid=[None]*H
for i in range(H):
  grid[i]=input()
  
from collections import deque
ans=0
for y1 in range(H):
  for x1 in range(W):
    for y2 in range(H):
      for x2 in range(W):
        if grid[y2][x2]=="#" or grid[y1][x1]=="#":
          continue
        q=deque()
        q.append([y1,x1,0])
        seen=[[False for j in range(W)] for i in range(H)]
        while q:
          node=q.popleft()
          y=node[0]
          x=node[1]
          dist=node[2]
          if seen[y][x]:
            continue
          if grid[y][x]=="#":
            continue
          if y==y2 and x==x2:
            if ans<dist:
              ans=dist
          seen[y][x]=True
          if y-1>=0:
            q.append([y-1,x,dist+1])
          if y+1<H:
            q.append([y+1,x,dist+1])
          if x-1>=0:
            q.append([y,x-1,dist+1])
          if x+1<W:
            q.append([y,x+1,dist+1])
            
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
grid=[None]*H
for i in range(H):
  grid[i]=input()
  
from collections import deque
ans=0

INF=10**9
ans=0
for i in range(H):
  for j in range(W):
    dist=[[INF for j in range(W)] for i in range(H)]
    q=deque()
    q.append([i,j,0])
    while q:
      node=q.popleft()
      y=node[0]
      x=node[1]
      d=node[2]
      if grid[y][x]=="#":
        continue
      if dist[y][x]<=d:
        continue
      if ans<d:
        ans=d
      dist[y][x]=d
      cases=((0,1),(0,-1),(1,0),(-1,0))
      for c in cases:
        if 0<=y+c[0]<H and 0<=x+c[1]<W:
          q.append([y+c[0],x+c[1],d+1])
      
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))
ans = -10**18
for i in range(n):  # 開始点を全通り
  x = i
  sc = []
  tot = 0
  while True:
    x = P[x]
    sc.append(C[x])
    tot += C[x]
    if x == i: break  # 開始点に戻ってきて循環に入った
  #print(i, sc, tot)
  l = len(sc)
  cum = 0
  for j in range(l):  # 何ステップ進むとよいか
    cum += sc[j]
    if j+1 > k: break  # k=1は最初の1周のみ
    val = cum  # 循環ループ考慮するスコア
    if tot > 0:
      cyc = (k-(j+1)) // l  # 残りステップで循環できる数
      val += tot * cyc
    ans = max(ans, val)
    #print(j, cum, cyc, val)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(lambda x: int(x)-1, input().split()))
C = list(map(int, input().split()))
ans = -10**18
for i in range(n):  # 開始点を全通り
  x = i
  sc = []
  tot = 0
  while True:
    x = P[x]
    sc.append(C[x])
    tot += C[x]
    if x == i: break  # 開始点に戻ってきて循環に入った
  #print(i, sc, tot)
  l = len(sc)
  cum = 0
  for j in range(l):  # 何ステップ進むとよいか
    cum += sc[j]
    if j+1 > k: break  # k=1は最初の1周のみ
    val = cum  # 循環ループ考慮するスコア
    if tot > 0:
      cyc = (k-(j+1)) // l  # 残りステップで循環できる数
      val += tot * cyc
    ans = max(ans, val)
    #print(j, cum, cyc, val)
print(ans)
### BUGGY CODE ###

from itertools import permutations

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

d = [list(map(int, input().split()))  for i in range(C)] 
c = [list(map(int, input().split()))  for i in range(N)] 

# 3行にまとめる
c_listed = [[],[],[]]

for i in range(N):
    for j in range(N):
        index = (i + j) % 3
        c_listed[index].append(c[i][j])



# 色の選び方
color_seq = permutations(range(C), 3)

ret = N * N * 1000
for color in color_seq:
    count = 0
    for line, line_color in zip(c_listed, color):
        for f in line:
            # f to line_color
            count += d[f-1][line_color]

    # 
    if count < ret:
        ret = count

print(ret)



### FIXED CODE ###

from itertools import permutations

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

d = [list(map(int, input().split()))  for i in range(C)] 
c = [list(map(int, input().split()))  for i in range(N)] 

# 3行にまとめる
c_listed = [{},{},{}]

for i in range(N):
    for j in range(N):
        index = (i + j) % 3
        c_listed[index][c[i][j]] = c_listed[index].get(c[i][j], 0) + 1

# 色の選び方
color_seq = permutations(range(C), 3)

ret = N * N * 1000
for color in color_seq:
    count = 0
    for line, line_color in zip(c_listed, color):
        for f, v in line.items():
            # f to line_color
            count += d[f-1][line_color] * v

    # 
    if count < ret:
        ret = count

print(ret)
### BUGGY CODE ###

h,w = map(int,input().split())
n = int(input())
a = list(map(int,input().split()))

c = [[0] * w for _ in range(h)]
li = [[0,0]]
hw = [0,0]
dir = 'r'

while len(li) < h*w:
    if dir == 'r':
        if hw[1] < h-1:
            if [hw[0], hw[1]+1] not in li:
                hw[1] += 1
            else:
                dir = 'd'
        else:
            dir = 'd'
    elif dir == 'd':
        if hw[0] < w-1:
            if [hw[0]+1, hw[1]] not in li:
                hw[0] += 1
            else:
                dir = 'l'
        else:
            dir = 'l'
    elif dir == 'l':
        if hw[1] > 0:
            if [hw[0], hw[1]-1] not in li:
                hw[1] -= 1
            else:
                dir = 'u'
        else:
            dir = 'u'
    else:
        if hw[0] > 0:
            if [hw[0]-1, hw[1]] not in li:
                hw[0] -= 1
            else:
                dir = 'r'
        else:
            dir = 'r'
    if hw not in li:
        li.append([hw[0], hw[1]])

count = 0

for i in range(n):
    for _ in range(a[i]):
        c[li[count][1]][li[count][0]] = i+1
        count += 1

for i in range(h):
    for j in range(w):
        print(c[i][j],end = ' ')
    print()


### FIXED CODE ###

h,w = map(int,input().split())
n = int(input())
a = list(map(int,input().split()))

c = [[0] * w for _ in range(h)]
li = [[0,0]]
hw = [0,0]
dir = 'r'

while len(li) < h*w:
    if dir == 'r':
        if hw[1] < h-1:
            if [hw[0], hw[1]+1] not in li:
                hw[1] += 1
                li.append([hw[0], hw[1]])
            else:
                dir = 'd'
        else:
            dir = 'd'
    elif dir == 'd':
        if hw[0] < w-1:
            if [hw[0]+1, hw[1]] not in li:
                hw[0] += 1
                li.append([hw[0], hw[1]])
            else:
                dir = 'l'
        else:
            dir = 'l'
    elif dir == 'l':
        if hw[1] > 0:
            if [hw[0], hw[1]-1] not in li:
                hw[1] -= 1
                li.append([hw[0], hw[1]])
            else:
                dir = 'u'
        else:
            dir = 'u'
    else:
        if hw[0] > 0:
            if [hw[0]-1, hw[1]] not in li:
                hw[0] -= 1
                li.append([hw[0], hw[1]])
            else:
                dir = 'r'
        else:
            dir = 'r'

count = 0

for i in range(n):
    for _ in range(a[i]):
        c[li[count][1]][li[count][0]] = i+1
        count += 1

for i in range(h):
    for j in range(w):
        print(c[i][j],end = ' ')
    print()
### BUGGY CODE ###

from collections import Counter

N=int(input())
L=[]
V=[]

for i in range(N):
    si=input()
    ci=Counter(si)
    c=sorted(ci.elements())
    v=L.count(c)
    if v==0:
        L.append(c)
        V.append(1)
    else:
        ind=L.index(c)
        V[ind]+=1


ans=0

for v in V:
    ans+=v*(v-1)//2

print(ans)

### FIXED CODE ###

from collections import Counter

N=int(input())
dic={}

ans=0

for i in range(N):
    si=input()
    # ci=Counter(si)
    # c=sorted(ci.elements())
    # c=sorted(Counter(si).elements())
    sorted_s=''.join(sorted(Counter(si).elements()))
    if sorted_s in dic:
        ans+=dic[sorted_s]
        dic[sorted_s]+=1
    else:
        dic[sorted_s]=1
print(ans)
### BUGGY CODE ###

def main():
  _max = max
  h, w = map(int, input().split())
  s = [input() for _ in range(h)]

  rt = [[-1] * w for _ in range(h + 1)]

  tstart = [-1] * (w)
  for i in range(h):
    si = s[i]
    rti = rt[i]
    ystart = -1
    for j in range(w):
      tj = tstart[j]
      if si[j] == '#':
        if ystart != -1:
          jy = j - ystart
          for k in range(ystart, j):
            rti[k] += jy
          ystart = -1
        if tj != -1:
          itj = i - tj
          for k in range(tj, i):
            rt[k][j] += itj
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tj == -1:
          tstart[j] = i

    if ystart != -1:
      jy = w - ystart
      for k in range(ystart, w):
        rti[k] += jy

  for j in range(w):
    tj = tstart[j]
    if tj != -1:
      itj = h - tj
      for k in range(tj, h):
        rt[k][j] += itj
      tstart[j] = -1

  print(_max(sum(rt, [])))

main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

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

### FIXED CODE ###

n,k = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab.sort()
tmp=0
i=0

while tmp<k:
  tmp+=ab[i][1]
  hoge=ab[i][0]
  i+=1

print(hoge)