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

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
def main():
    N = int(input())
    l = []
    for i in range(N):
        a = list(map(int, input().split()))
        for j in range(N):
            if i < j:
                l.append((a[j], i, j))
    l.sort()
    r = [[0]*N for _ in range(N)]
    ans = 0
    for k, i, j in l:
        G = csr_matrix(r)
        d = dijkstra(G, indices=i)
        if d[j] < k:
            return -1
        elif d[j] == k:
            continue
        else:
            r[i][j] = k
            r[j][i] = k
            ans += k
    return ans
print(main())


### FIXED CODE ###

def main():
    N = int(input())
    l = []
    for i in range(N):
        a = list(map(int, input().split()))
        l.append(a)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if i == j:
                continue
            for k in range(N):
                if k == i or k == j:
                    continue
                if l[i][j] == l[i][k] + l[k][j]:
                    break
                if l[i][j] > l[i][k] + l[k][j]:
                    return -1
            else:
                ans += l[i][j]
    return ans
print(main())
### BUGGY CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
C = []
for _ in range(m):
    b, c = map(int, input().split())
    for i in range(b):
        C.append(c)
A.extend(C)

A = sorted(A, reverse=True)
result = [A[i] for i in range(n)]
print(sum(result))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
answer = 0
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

for ai in a:
    # print(prime_decomposition(ai))
    # # if 2 in prime_decomposition:
    # #     print('Yes')
    # print(prime_decomposition(ai).count(2))
    answer += prime_decomposition(ai).count(2)

print(answer)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
answer = 0
# def prime_decomposition(n):
#   i = 2
#   table = []
#   while i * i <= n:
#     while n % i == 0:
#       n /= i
#       table.append(i)
#     i += 1
#   if n > 1:
#     table.append(n)
#   return table
def count2(n):
    count = 0
    while True:
        if n % 2 == 0:
            n //= 2
            count += 1
        else:
            break
    return count  

for ai in a:
    # print(prime_decomposition(ai))
    # print(prime_decomposition(ai).count(2))
    answer += count2(ai)

print(answer)
### BUGGY CODE ###

import sys
bbn=1000000007
	
#+++++

def modinv(a,m):
	b=m
	u=1
	v=0
	
	while b > 0:
		t = a //b
		a = a - (t * b)
		a,b = b,a
		u = u - (t * v)
		u,v=v,u
	
	u = u % m
	if u < 0:
		u+=m
	return u

def gcd(a,b):
	while b!= 0:
		a,b=b,a%b
		
	return a
		
def main():
	n = int(input())
	al = list(map(int, input().split()))
	
	#saisyoukoubausuu
	ss=1
	for v in al:
		ss = ss*v//gcd(ss,v) 
		#ss %= bbn
	
	ret=0
	for v in al:
		ret+=(ss * modinv(v,bbn))
		ret%=bbn
		
	
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
bbn=1000000007
	
#+++++

def modinv(a,m):
	b=m
	u=1
	v=0
	
	while b > 0:
		t = a //b
		a = a - (t * b)
		a,b = b,a
		u = u - (t * v)
		u,v=v,u
	
	u = u % m
	if u < 0:
		u+=m
	return u

def gcd(a,b):
	while b!= 0:
		a,b=b,a%b
		
	return a
		
def main():
	n = int(input())
	al = list(map(int, input().split()))
	
	#saisyoukoubausuu
	ss=1
	for v in al:
		ss = ss * v //gcd(ss,v)
		#ss %= bbn
	
	ss=ss%bbn
	ret=0
	for v in al:
		ret += ss *modinv(v, bbn)
		ret%=bbn
		
	
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
neighbor = [[] for _ in range(n)]
point = [0]*n

for i in range(n-1):
    a, b = map(int, input().split())
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)

for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x


def dfs(now, past):
    for nv in neighbor[now]:
        if nv == past:
            continue
        point[nv] += point[now]
        dfs(nv, now)


dfs(0, -1)


print(*point)


### FIXED CODE ###

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

n, q = map(int, input().split())
neighbor = [[] for _ in range(n)]
point = [0]*n

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    neighbor[a].append(b)
    neighbor[b].append(a)

for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x


def dfs(now, past):
    for nv in neighbor[now]:
        if nv == past:
            continue
        point[nv] += point[now]
        dfs(nv, now)


dfs(0, -1)


print(*point)
### BUGGY CODE ###

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

for i in range(n):
    x[i]=x[i]-a
    
# itertools 使用 bit全探索
import itertools
icnt=0
for i in itertools.product([0,1], repeat=n):
    isum=0
    for ii in range(n):
#        if i[ii]==0:
        isum=isum+x[ii]*i[ii]
    if isum==0:
        icnt=icnt+1

print(icnt-1)

### FIXED CODE ###

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

for i in range(n):
    x[i]=x[i]-a
    
nx=n*n
dp=[[0]*(2*nx+1) for i in range(n+1)]

#print(dp)

dp[0][nx]=1

for j in range(1,n+1):
    jj=j-1
    for t in range(2*nx+1):
        if t-x[jj]<0 or 2*nx<t-x[jj]:
            dp[j][t]=dp[j-1][t]
        elif 0<t-x[jj] and  t-x[jj]<2*nx:
            dp[j][t]=dp[j-1][t]+dp[j-1][t-x[jj]]
        else:
            dp[j][t]=0

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

n, k = map(int, input().split())
a = list(map(int, input().split()))
r = 0
s = {0: [0]}
for i in range(n):
    r = (r + a[i] - 1) % k
    s[r] = s.get(r, []) + [i + 1]
ret = 0
for key in s:
    a = s[key]
    en = 0
    for st in range(len(a)):
        while en < len(a) and a[en] - a[st] < k:
            en += 1
        ret += en - st - 1
print(ret)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
r = 0
s = {0: [0]}
for i in range(n):
    r = (r + a[i] - 1) % k
    if r in s:
        s[r].append(i + 1)
    else:
        s[r] = [i + 1]
ret = 0
for key in s:
    a = s[key]
    en = 0
    for st in range(len(a)):
        while en < len(a) and a[en] - a[st] < k:
            en += 1
        ret += en - st - 1
print(ret)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
def main():
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
			break
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > 10**7:
			print(-1)
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
def main():
	limit = 10 ** 4
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > limit:
			print(n*(n-1)//2)
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
hw = []
for i in range(h):
    hw.append(input())

# used = [True]*h*w
isWhite = [[True]*w for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if hw[i][j] == '#':
            queue.append([i,j])
            isWhite[i][j] = False

res = 0
while queue:
    nextQueue = []
    for pos in queue:
        if pos[0] > 0 and isWhite[pos[0]-1][pos[1]]:
            nextQueue.append([pos[0]-1,pos[1]])
            isWhite[pos[0]-1][pos[1]] = False
        if pos[0] < h-1 and isWhite[pos[0]+1][pos[1]]:
            nextQueue.append([pos[0]+1,pos[1]])
            isWhite[pos[0]+1][pos[1]] = False
        if pos[1] > 0 and isWhite[pos[0]][pos[1]-1]:
            nextQueue.append([pos[0],pos[1]-1])
            isWhite[pos[0]][pos[1]-1] = False
        if pos[1] < w-1 and isWhite[pos[0]][pos[1]+1]:
            nextQueue.append([pos[0],pos[1]+1])
            isWhite[pos[0]][pos[1]+1] = False
    queue = nextQueue
    res += 1
print(res-1)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())

field = [] # 白黒情報を持つリスト
mark = [] # 操作回数を保持するリスト
INF = 10**6

for i in range(h):
    field.append(list(input()))
    mark.append([0 for i in range(w)])

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

queue = deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            queue.append([i, j])

while len(queue) > 0:
    y, x = queue.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= ny < h and 0 <= nx < w:
            if field[ny][nx] == ".":
                mark[ny][nx] = mark[y][x] + 1
                queue.append([ny, nx])
                field[ny][nx] = "#"

ans=0

for i in mark:
    ans = max(ans, max(i))

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

n,m = list(map(int,input().split()))
a = [[0] for i in range(n)]
b = [None]*m
for i in range(m):
    p,s = list(map(int,input().split()))
    p-=1
    a[p].append(s)
    b[i] = [p,s]
for i in range(len(a)):
    a[i].sort()
for i in range(len(b)):
    ken = b[i][0]
    si = a[ken].index(b[i][1])
    ken = str(ken+1).zfill(6)
    si = str(si).zfill(6)
    print("".join([ken,si]))

### FIXED CODE ###

from bisect import bisect_left


n,m = list(map(int,input().split()))
a = [[0] for i in range(n)]
b = [None]*m
for i in range(m):
    p,s = list(map(int,input().split()))
    p-=1
    a[p].append(s)
    b[i] = [p,s]
for i in range(len(a)):
    a[i].sort()
for i in range(len(b)):
    ken = b[i][0]
    si = bisect_left(a[ken], b[i][1])
    ken = str(ken+1).zfill(6)
    si = str(si).zfill(6)
    print("".join([ken,si]))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

h, n = map(int, input().split())
ab = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [10 ** 20] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        if dp[i + a] > dp[i] + b:
            dp[i + a] = dp[i] + b
print(min(dp[h:]))

### FIXED CODE ###

h, n = map(int, input().split())
ab = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [10 ** 20] * 10 ** 4 * 2
dp[0] = 0
for a, b in ab:
    for i in range(h):
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))
### BUGGY CODE ###

N = int(input())
num = 2
idx = 1
nums = []
while True:
  if num**idx > N:
    if idx == 2:
      break
    else:
      num += 1
      idx = 0
      continue
  else:
    nums.append(num**idx)
    idx += 1
nums.sort(key=lambda x:-x)
print(nums[0])

### FIXED CODE ###

N = int(input())
num = 2
idx = 1
nums = [1]
while True:
  if num**idx > N:
    if idx == 2 or N in range(1, 5):
      break
    else:
      num += 1
      idx = 0
      continue
  else:
    nums.append(num**idx)
    idx += 1
nums.sort(key=lambda x:-x)
print(nums[0])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]

box = []
for i in range(N):
    box.append(S[:i+1].count("AC"))

for i, j in lr:
    print(box[j-1] - box[i-1])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
l, r = [], []
t = [0] * (N+1)
for i in range(N):
    t[i + 1] = t[i] +(1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

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

import sys
from collections import deque, defaultdict
from copy import deepcopy

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S = input()
T = input()
N = len(S)

d = defaultdict(deque)
for i, s in enumerate(S):
    d[s].append(i)

d2 = deepcopy(d)
cur = -1
ans = 0
for i, t in enumerate(T):
    if t not in d2:
        print(-1)
        exit()
    if len(d2[t]) == 0:
        ans += N
        d2 = deepcopy(d)
        cur = -1 
    idx = d2[t].popleft()
    if idx < cur:
        ans += N
        d2 = deepcopy(d)
    cur = idx
ans += cur+1
print(ans)


### FIXED CODE ###

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

import sys
from collections import defaultdict
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S = input()
T = input()
N = len(S)

d = defaultdict(list)
for i, s in enumerate(S):
    d[s].append(i)
for k, v in d.items():
    d[k].append(INF)

cur = -1
ans = 0
for i, t in enumerate(T):
    if t not in d:
        print(-1)
        exit()
    idx = bisect_right(d[t], cur)
    if d[t][idx] == INF:
        ans += N
        cur = d[t][0]
    else:
        cur = d[t][idx]
ans += cur+1
print(ans)
### BUGGY CODE ###

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

previous_score = 1

for i in range(k):
    previous_score *= a[i] 

for j in range(k, n):
    score = previous_score * a[j] / a[j-k]

    if previous_score < score:
        print('Yes')
    else:
        print('No')

    previous_score = score

### FIXED CODE ###

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

for i in range(k, n):
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

a,b,k = map(int, input().split())
for i in range(k):
    if a > 0:
        a -= 1
    elif b > 0:
        b -= 1
print(str(a) + " " + str(b))

### FIXED CODE ###

a,b,k = map(int, input().split())
if k <= a:
    a -= k
elif k <= a + b:
    b = a + b - k
    a = 0
else:
    a = 0
    b = 0
print(str(a) + " " + str(b))
### BUGGY CODE ###

N = int(input())
A = [int(v) for v in input().split()]
MOD = int(1e9 + 7)
s = 0
L = {}
for i in range(N):
    for j in range(i+1, N):
        if (A[i], A[j]) in L or (A[j], A[i]) in L:
            s = (s + L[(A[i], A[j])]) % MOD
        else:
            r = (A[i] * A[j])
            s = (s + r) % MOD
            L[(A[i], A[j])] = r
            L[(A[j], A[i])] = r

print(s)

### FIXED CODE ###

N = int(input())
A = [int(v) for v in input().split()]
MOD = int(1e9 + 7)

S = sum(A)
SQ = S * S
IS = sum(a*a for a in A)

print(((SQ - IS) // 2) % MOD)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    d = m = dm = dmc = 0
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                d -= 1
                dm -= m
            elif S[j] == 'M' :
                m -= 1

        if S[i] == 'D' :
            d += 1
        elif S[i] == 'M' :
            m += 1
            dm += d
        elif S[i] == 'C' :
            dmc += dm
            
    print(dmc)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)
### BUGGY CODE ###

import numpy as np
import sys
a,b,k = map(int,input().split())
for i in range(b-a+1):
    if i < k or b-a-i < k:
        print(a+i)


### FIXED CODE ###

import numpy as np
import sys
a,b,k = map(int,input().split())
for i in range(k):
    if i <= b-a:
        print(a+i)
for i in range(k):
    if k-i-1 <= b-a-k:
        print(b-k+i+1)
### BUGGY CODE ###

N,K = map(int, input().split())
d = [0]*2*K
for i in range(K):
    d[2*i], d[2*i+1] = map(int, input().split())
a=[0]*(N+1)
b=[0]*(N+1)
a[1]=1
b[1]=1
for i in range(2,N+1):
    t=0
    for j in range(K):
        if i-d[2*j]>0:
            t+=b[i-d[2*j]]
        if i-d[2*j+1]-1>0:
            t-=b[i-d[2*j+1]-1]
    a[i]=t
    b[i]=b[i-1]+a[i]
print(a[N]%998244353)


### FIXED CODE ###

N,K = map(int, input().split())
d = [0]*2*K
for i in range(K):
    d[2*i], d[2*i+1] = map(int, input().split())
a=[0]*(N+1)
b=[0]*(N+1)
a[1]=1
b[1]=1
for i in range(2,N+1):
    t=0
    for j in range(K):
        if i-d[2*j]>0:
            t+=b[i-d[2*j]]
        if i-d[2*j+1]-1>0:
            t-=b[i-d[2*j+1]-1]
    a[i]=t
    b[i]=(b[i-1]+a[i])%998244353
print(a[N]%998244353)
### BUGGY CODE ###

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

### FIXED CODE ###

n, k, q = map(int, input().split())
b = [k - q] * n

for i in range(q):
    ai = int(input())
    b[ai - 1] += 1

for j in range(n):
    if b[j] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def main():
    from itertools import accumulate as ac
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    s = set()
    loop = []
    for i in range(n):
        if i not in s:
            j = i
            temp = [c[j]]
            s.add(j)
            while True:
                j = p[j]-1
                if j not in s:
                    temp.append(c[j])
                    s.add(j)
                else:
                    break
            loop.append(temp+temp)
    ans = -10**15
    for l in loop:
        m = len(l)//2
        s = max(0, sum(l)//2)
        l = [0]+list(ac(l))
        temp = [-10**15]*m
        for i in range(m):
            for j in range(i+1, i+m+1):
                width = j-i-1
                temp[width] = max(temp[width], l[j]-l[i])
        for i in range(m):
            if k-i-1 >= 0:
                ans = max(ans, ((k-i-1) // m)*s+temp[i])
    print(ans)


main()


### FIXED CODE ###

def main():
    from itertools import accumulate as ac
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    s = set()
    loop = []
    for i in range(n):
        if i not in s:
            j = i
            temp = [c[j]]
            s.add(j)
            while True:
                j = p[j]-1
                if j not in s:
                    temp.append(c[j])
                    s.add(j)
                else:
                    break
            loop.append(temp+temp)
    ans = -10**15
    for l in loop:
        m = len(l)//2
        s = max(0, sum(l)//2)
        l = [0]+list(ac(l))
        temp = [-10**15]*m
        for i in range(m):
            for j in range(i+1, i+m+1):
                width = j-i-1
                temp[width] = max(temp[width], l[j]-l[i])
        for i in range(m):
            if k-i-1 >= 0:
                ans = max(ans, ((k-i-1) // m)*s+temp[i])
    print(ans)


main()
### BUGGY CODE ###

def solve(n, t, ab_list):
    a0b_list = [ab[1] for ab in ab_list if ab[0] == 0]
    apb_list = [ab for ab in ab_list if ab[0] > 0]
    a0b_list = sorted(a0b_list)
    apb_list = sorted(apb_list, key=lambda x: - x[0] / (x[1] + 1))
    # DP
    m = len(apb_list)
    dp = [[t + 1] * 30 for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = 0
    for i in range(m):
        for k in range(1, 30):
            ti = dp[i][k - 1] + 1
            a, b = apb_list[i]
            dp[i + 1][k] = min(dp[i][k], ti + a * ti + b)
    a0b_list_cum_sum = [0]
    s = 0
    for b in a0b_list:
        s += b + 1
        a0b_list_cum_sum.append(s)

    res = 0

    for k in range(len(a0b_list_cum_sum)):
        for p in range(30):
            if dp[m][p] + a0b_list_cum_sum[k] <= t:
                res = max(res, k + p)
                
    return res


def main():
    n, t = map(int, input().split())
    ab_list = [list(map(int, input().split())) for _ in range(n)]
    res = solve(n, t, ab_list)
    print(res)


def test():
    assert solve(3, 7, [[2, 0], [3, 2], [0, 3]]) == 2
    assert solve(1, 3, [[0, 3]]) == 0
    assert solve(5, 21600, [[2, 14], [3, 22], [1, 3], [1, 10], [1, 9]]) == 5


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

def solve(n, t, ab_list):
    a0b_list = [ab[1] for ab in ab_list if ab[0] == 0]
    apb_list = [ab for ab in ab_list if ab[0] > 0]
    a0b_list = sorted(a0b_list)
    apb_list = sorted(apb_list, key=lambda x: - x[0] / (x[1] + 1))
    # DP
    m = len(apb_list)
    dp = [[t + 1] * 30 for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = 0
    for i in range(m):
        for k in range(1, 30):
            ti = dp[i][k - 1] + 1
            a, b = apb_list[i]
            dp[i + 1][k] = min(dp[i][k], ti + a * ti + b)
    a0b_list_cum_sum = [0]
    s = 0
    for b in a0b_list:
        s += b + 1
        a0b_list_cum_sum.append(s)

    res = 0

    for k in range(len(a0b_list_cum_sum)):
        for p in range(30):
            if dp[m][p] + a0b_list_cum_sum[k] <= t:
                res = max(res, k + p)

    return res


def main():
    n, t = map(int, input().split())
    ab_list = [list(map(int, input().split())) for _ in range(n)]
    res = solve(n, t, ab_list)
    print(res)


def test():
    assert solve(3, 7, [[2, 0], [3, 2], [0, 3]]) == 2
    assert solve(1, 3, [[0, 3]]) == 0
    assert solve(5, 21600, [[2, 14], [3, 22], [1, 3], [1, 10], [1, 9]]) == 5


if __name__ == "__main__":
    test()
    main()