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

from collections import Counter

def main():
    n = int(input().strip())
    s = list(input().strip())

    bit = [Counter() for _ in range(n + 1)]

    def query(i):
        result = Counter()
        while i:
            result += bit[i]
            i -= i & -i
        return result
    
    def update(i, cnt):
        while i < len(bit):
            bit[i] += cnt
            i += i & -i

    for i, c in enumerate(s, 1):
        update(i, {c: 1})

    q = int(input().strip())
    for _ in range(q):
        Q = input().strip().split()
        if Q[0] == "1":
            i, c = int(Q[1]), Q[2]
            if s[i - 1] != c:
                update(i, {s[i - 1]: -1, c: 1})
                s[i - 1] = c
        else:
            cnt = query(int(Q[2])) - query(int(Q[1]) - 1)
            print(len(cnt))


main()


### FIXED CODE ###

def main():
    n = int(input().strip())
    s = list(input().strip())

    bit = [[0] * 26 for _ in range(n + 1)]

    def query(i):
        result = [0] * 26
        while i:
            for j, x in enumerate(bit[i]):
                result[j] += x
            i -= i & -i
        return result
    
    def update(i, c, val):
        j = ord(c) - ord("a")
        while i < len(bit):
            bit[i][j] += val
            i += i & -i

    for i, c in enumerate(s, 1):
        update(i, c, 1)

    q = int(input().strip())
    for _ in range(q):
        Q = input().strip().split()
        if Q[0] == "1":
            i, c = int(Q[1]), Q[2]
            update(i, s[i - 1], -1)
            update(i, c, 1)
            s[i - 1] = c
        else:
            l, r = int(Q[1]), int(Q[2])
            cnt = [x - y for x, y in zip(query(r), query(l - 1))]
            print(sum(x > 0 for x in cnt))


main()
### BUGGY CODE ###

inf = float("INF")
x,y,z,k=map(int,input().split())
dp=[0]*3000
l =[]
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
for i in a:
  for j in b:
    l.append(i+j)
l.sort()
l = l[::-1]
t =[]
for i in l[:k]:
  for j in c:
    t.append(i+j)
t.sort()
t = t[::-1]
for i ,n in enumerate(t):
  print(n)
  if i == k-1:break

### FIXED CODE ###

inf = float("INF")
x,y,z,k=map(int,input().split())
dp=[0]*3000
l =[]
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
for i in a:
  for j in b:
    l.append(i+j)
l.sort()
l = l[::-1]
t =[]
for i in l[:k]:
  for j in c:
    t.append(i+j)
t.sort()
t = t[::-1]
for i ,n in enumerate(t):
  print(n)
  if i == k-1:break
### BUGGY CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]

log = []
button = 1
count = 0
while button != 2:
    button = a[button-1]
    if (button in log) == True:
        count = -1
        break
    count += 1
    log.append(button)
print(count)

### FIXED CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]

log = []
button = 1
count = 0
while button != 2:
    button = a[button-1]
    count += 1
    log.append(button)
    if count == N+1:
        count = -1
        break
print(count)
### BUGGY CODE ###

from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    abc=np.array([list(map(int,readline().split())) for _ in range(n)],dtype=np.int64)

    x=np.array([1,2])
    y=np.array([2,0])
    z=np.array([0,1])

    dp=np.zeros((n+1,3),dtype=np.int64)
    for i in range(n):
        dp[i+1,x]=np.maximum(dp[i+1,x],dp[i][0]+abc[i,x])
        dp[i+1,y]=np.maximum(dp[i+1,y],dp[i][1]+abc[i,y])
        dp[i+1,z]=np.maximum(dp[i+1,z],dp[i][2]+abc[i,z])

    print(dp[-1].max())

if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N=int(input())
    abc=[0]*N
    for i in range(N):
        xyz=list(map(int,input().split()))
        abc[i]=xyz
    dp=[[0]*3 for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(3):
            dp[i][j]=max(dp[i-1][(j-1)%3]+abc[i-1][(j-1)%3],dp[i-1][(j-2)%3]+abc[i-1][(j-1)%3])

    print(max(max(dp[N][0],dp[N][1]),dp[N][2]))

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

from functools import reduce
from operator import mul

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

seki = reduce(mul, l)
max = 1000000000000000000
print(-1 if seki > max else seki)

### FIXED CODE ###

from functools import reduce
from operator import mul
import math

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

    if 0 in l:
        print(0)
        return
    l_sorted = sorted(l, reverse=True)
    log = 0
    seki = 1
    for i in l_sorted:
        log += math.log10(i)
        if log > 18:
            print(-1)
            return
        elif log == 18:
            seki *= i
            if seki != 10 ** 18:
                print(-1)
                return
        else:
            seki *= i
    print(seki)
    return


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

from math import sqrt
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

xs, ys, xt, yt = map(int, input().split())
n = int(input())
xyr = [list(map(int, input().split())) for _ in range(n)]

xyr.append([xs, ys, 0])
xyr.append([xt, yt, 0])

row = []
col = []
cost = []

for i, (xi, yi, ri) in enumerate(xyr):
    for j, (xj, yj, rj) in enumerate(xyr):
        row.append(i)
        col.append(j)
        dist = max(0, sqrt((xi - xj) ** 2 + (yi - yj) ** 2) - ri - rj)
        cost.append(dist)

g = csr_matrix((cost, (row, col)), shape=(n + 2, n + 2))
d = dijkstra(g, indices=n)
ans = d[n+1]
print(ans)


### FIXED CODE ###

from math import sqrt
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

xs, ys, xt, yt = map(int, input().split())
n = int(input())
xyr = [list(map(int, input().split())) for _ in range(n)]

xyr.append([xs, ys, 0])
xyr.append([xt, yt, 0])

row = []
col = []
cost = []

for i, (xi, yi, ri) in enumerate(xyr):
    for j, (xj, yj, rj) in enumerate(xyr[i+1:], i+1):
        row.append(i)
        col.append(j)
        dist = max(0, sqrt((xi - xj) ** 2 + (yi - yj) ** 2) - ri - rj)
        cost.append(dist)

g = csr_matrix((cost, (row, col)), shape=(n + 2, n + 2))
d = dijkstra(g, directed=False, indices=n)
ans = d[n+1]
print(ans)
### BUGGY CODE ###

s = input()[::-1]

mod = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(len(s)+1)]

dp[0][0] = 1
keta = 1
for i in range(len(s)):
    for j in range(13):
        if s[i] == '?':
            for k in range(10):
                dp[i+1][(k*keta+j)%13] += dp[i][j] 
                dp[i+1][(k*keta+j)%13] %= mod 
        else:
            dp[i+1][((int(s[i]))*keta+j)%13] += dp[i][j] 
            dp[i+1][((int(s[i]))*keta+j)%13] %= mod
    keta = (keta * 10) % 13

print(dp[-1][5]%mod)

### FIXED CODE ###

s = input()[::-1]

mod = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(len(s)+1)]

dp[0][0] = 1
keta = 1
for i in range(len(s)):
    for j in range(13):
        if s[i] == '?':
            for k in range(10):
                dp[i+1][(k*keta+j)%13] += dp[i][j] 
                dp[i+1][(k*keta+j)%13] %= mod 
        else:
            dp[i+1][((int(s[i]))*keta+j)%13] += dp[i][j] 
            dp[i+1][((int(s[i]))*keta+j)%13] %= mod
    keta = (keta * 10) % 13

print(dp[-1][5]%mod)
### BUGGY CODE ###

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

A = 0

for i in range(N):
  if P[i] <= min(P[0:i+1]):
  	A += 1
  if P[i] == 1:
    break
  elif P[i] == 2:
    A+=1
    break
print(A)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
 
A = 0
C = P[0]
for i in range(N):
  if P[i] <= C:
    C = P[i]
    A += 1
print(A)
### BUGGY CODE ###

S = input()
Q = int(input())

for i in range(Q):
  query = input()
  if query=='1':
    S = S[::-1]
  else:
    _, F, C = query.split()
    if F=='1':
      S = C+S
    else:
      S = S+C

print(S)


### FIXED CODE ###

S = input()
Q = int(input())

add_to_last = []
add_to_beginning = []

queries = [input() for _ in range(Q)]

mode = 1
for i in range(Q):
  query = queries[i]
  if query=='1':
    mode *= -1
  else:
    _, F, C = query.split()
    if F=='1':
      if mode==1:
        add_to_beginning.append(C)
      else:
        add_to_last.append(C)
    else:
      if mode==1:
        add_to_last.append(C)
      else:
        add_to_beginning.append(C)   

if mode==1:
  add_to_beginning.reverse()
  print("".join(add_to_beginning), end="")
  print(S, end="")
  print("".join(add_to_last))
else:
  add_to_last.reverse()
  print("".join(add_to_last), end="")
  print(S[::-1], end="")
  print("".join(add_to_beginning))
### BUGGY CODE ###

N = int(input())
k = []
for i in range(N):
  k.append(int(input()))
p = k
x = k.index(max(k))
for i in range(N):
  if i==x:
    p.sort()
    print(p[-2])
  else:
    print(max(k))

### FIXED CODE ###

N = int(input())
k = []
for i in range(N):
    k.append(int(input()))
B = k.copy()
B.sort()
B.reverse()
P = B[0]
Q = B[1]
for i in range(N):
    if k[i] == P:
        print(Q)
    else:
        print(P)
### BUGGY CODE ###

#pdf解説をそのまま
n = int(input())

c = [[0]*10 for _ in range(10)]

for i in range(10):
    for j in range(10):
        for k in range(1,n+1):
            if str(k)[0] == str(i) and str(k)[-1] == str(j):
                c[i][j] += 1
                
ans = 0
for i in range(10):
    for j in range(10):
        ans += c[i][j] * c[j][i]

print(ans)
    

### FIXED CODE ###

#pdf解説をそのまま
n = int(input())

c = [[0]*10 for _ in range(10)]

for i in range(10):
    for j in range(10):
        for k in range(1,n+1):
            if str(k)[0] == str(i) and str(k)[-1] == str(j):
                c[i][j] += 1
                
ans = 0
for i in range(10):
    for j in range(10):
        ans += c[i][j] * c[j][i]

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

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

ans = 1
inf = 10**18 + 1
for i in a:
    ans *= i

ans = min(ans, inf)
if ans == inf:
    ans = -1

print(ans)

### FIXED CODE ###

n = int(input())
a = map(int, input().split())
a = sorted(a, reverse=True)
ans = 1

if 0 in a:
    print(0)
    exit()

for i in a:
    ans *= i
    if ans > 10**18:
        print(-1)
        exit()

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

n, k = map(int, input().split())
L = list(map(int, input().split()))
d = {}
for a in L:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
l = []
for v in d.values():
    l.append(v)

if len(l) <= k:
    print(0)
else:
    ans = float('inf')
    for i in range(2 ** len(l)):
        b = [0] * len(l)
        for j in range(len(l)):
            if ((i >> j) & 1):
                b[j] = 1
        if b.count(1) <= k:
            cnt = 0
            for m in range(len(l)):
                if b[m] == 0:
                    cnt += l[m]
            ans = min(ans, cnt)
    print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
L = list(map(int, input().split()))
d = {}
for a in L:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
l = []
for v in d.values():
    l.append(v)
l.sort(reverse=True)
print(n - sum(l[:k]))
### BUGGY CODE ###

def main():
    n=int(raw_input())
    a=map(int,raw_input().split())
    now=a
    while 1:
        l=len(now)
        if l==1:
            print(now[0])
            break
        if max(now[0:l/2])<=now[l/2]<=min(now[l/2+1:]):
            print(now[l/2])
            break
        if now[l/2-1]==now[l/2] or now[l/2]==now[l/2+1]:
            print(now[l/2])
            break
        if now[l/2-1]<now[l/2]<now[l/2+1]:
            if now[l/2-2]>=now[l/2]:
                print(now[l/2])
                break
            if now[l/2+2]<=now[l/2]:
                print(now[l/2])
                break
        if now[l/2+1]<now<now[l/2-1]:
            if now[l/2+2]>=now[n/l]:
                print(now[l/2])
                break
            if now[l/2-2]<=now[l/2]:
                print(now[l/2])
                break
        else:
            nx=[]
            for i in xrange(l-2):
                tmp=[]
                tmp.append(now[i])
                tmp.append(now[i+1])
                tmp.append(now[i+2])
                tmp.sort()
                nx.append(tmp[1])
            now=nx

main()

### FIXED CODE ###

def check(m):
    tmpa = [-1] * 2 * n
    for i in xrange(2 * n - 1):
        if a[i] < m:
            tmpa[i] = 0
        else:
            tmpa[i] = 1

    idx = n -1
    while idx < 2 * n - 1:
        idx += 1
        if tmpa[idx - 1] == tmpa[idx]:
            rr = tmpa[idx]
            ridx = idx - 1
            break
    else:
        rr = -1
        ridx = 2 * n - 1

    idx = n - 1
    while idx > 0:
        idx -= 1
        if tmpa[idx + 1] == tmpa[idx]:
            ll = tmpa[idx]
            lidx = idx + 1
            break
    else:
        ll = -1
        lidx = -1

    if rr == ll == -1:
        if n % 2 == 0:
            if tmpa[n - 1] == 1:
                return False
            else:
                return True
        else:
            if tmpa[n - 1] == 1:
                return True
            else:
                return False
    elif ridx - (n - 1) == (n - 1) - lidx:
        if rr != ll:
            if tmpa[n - 1] == 1:
                return True
            else:
                return False
        else:
            if rr==1:
                return True
            else:
                return False
    elif ridx - (n - 1) > (n - 1) -lidx:
        if ll == 1:
            return True
        else:
            return False
    else:
        if rr == 1:
            return True
        else:
            return False

n = int(raw_input())
a = map(int,raw_input().split())
l = 1
r = 2 * n
while r - l > 1:
    m = (r + l)/2
    if check(m):
        l = m
    else:
        r = m
print(l)
### BUGGY CODE ###

from collections import deque
N,M = map(int,input().split())
a = deque([int(input()) for m in range(M)])
ans = []
P = 10**9+7
for n in range(N):
    if n+1 in a:
        ans.append(0)
        a.popleft()
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])


### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())
a = deque([int(input()) for m in range(M)]+[-1])
ans = []
P = 10**9+7
for n in range(N):
    if n+1 == a[0]:
        ans.append(0)
        a.popleft()
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])
### BUGGY CODE ###

from sys import stdin

a, b = [int(x) for x in stdin.readline().split()]

while b != 0:
    a, b = b, a % b

c = 1
n = 0
while a % 2 == 0:
    a //= 2
    n += 1
if n > 0:
    c += 1
i = 3
while a > 1:
    n = 0
    while a % i == 0:
        a //= i
        n += 1
    if n > 0:
        c += 1
    i += 2

print(c)


### FIXED CODE ###

from sys import stdin

a, b = [int(x) for x in stdin.readline().split()]

while b != 0:
    a, b = b, a % b

c = 1
lim = a ** 0.5 + 10
n = 0
i = 2
while a > 1 and i <= lim:
    n = 0
    while a % i == 0:
        a //= i
        n += 1
    if n > 0:
        c += 1
    i += 1
if a > 1:
    c += 1

print(c)
### BUGGY CODE ###

import sys

H,W = map(int,input().split())
maze = [list(input()) for i in range(H)]

def removeWalls(wallPointH,wallPointW):
  if maze[wallPointH][wallPointW]=="#":
    maze[wallPointH][wallPointW]="."
    if wallPointH+1 <= H-1:
      removeWalls(wallPointH+1,wallPointW)
    if wallPointW+1 <= W-1:
      removeWalls(wallPointH,wallPointW+1)

que = [[0,0,0]]
count = 0
      
while que:
  #print(que)
  if que[0][0]==1:
    que.sort()
  if que[0][0]==1:
    count += 1
    for q in que:#いったん"#"の撤去作業を行う
      q[0]=0
      removeWalls(q[1],q[2])
  else:#queの中身にまだTrueがあるなら
    now = que.pop(0)
    nowH = now[1]
    nowW = now[2]
    if maze[nowH][nowW]=="#":#行き止まりの場合
      que.append([1,nowH,nowW])
      continue
    elif nowH==H-1 and nowW==W-1:#ゴールの場合
      print(count)
      sys.exit()
    else:#それ以外の場合
      #右近傍と下近傍、それぞれマップの中ならqueに格納。
      if nowH+1 <= H-1:
        que.append([0,nowH+1,nowW])
      if nowW+1 <= W-1:
        que.append([0,nowH,nowW+1])



### FIXED CODE ###

import sys
import heapq

H,W = map(int,input().split())
maze = [list(input()) for i in range(H)]

def removeWalls(wallPointH,wallPointW):
  if maze[wallPointH][wallPointW]=="#":
    changeTo = "."
  elif maze[wallPointH][wallPointW]=="1":
    changeTo = "0"
  if maze[wallPointH][wallPointW]=="#" or maze[wallPointH][wallPointW]=="1":
    maze[wallPointH][wallPointW]=changeTo
    if wallPointH+1 <= H-1:
      removeWalls(wallPointH+1,wallPointW)
    if wallPointW+1 <= W-1:
      removeWalls(wallPointH,wallPointW+1)

if maze[0][0]=="#":
  flag=1
else:
  flag=0
      
que = [[flag,0,0]]
heapq.heapify(que)
count = 0
      
while que:
  qu = heapq.heappop(que)
  if qu[0]==1:
    heapq.heappush(que, qu)
    count += 1
    for q in que:#いったん"#"の撤去作業を行う
      q[0]=0
      removeWalls(q[1],q[2])
  else:#queの中身にまだ進める場所があるなら
    nowH = qu[1]
    nowW = qu[2]
    if nowH==H-1 and nowW==W-1:#ゴールの場合
      print(count)
      sys.exit()
    else:#それ以外の場合
      #右近傍と下近傍、それぞれマップの中ならqueに格納。
      if nowH+1 <= H-1:
        if maze[nowH+1][nowW]=="#":
          maze[nowH+1][nowW]="1"
          heapq.heappush(que, [1,nowH+1,nowW])
        elif maze[nowH+1][nowW]==".":
          maze[nowH+1][nowW]="0"
          heapq.heappush(que, [0,nowH+1,nowW])
      if nowW+1 <= W-1:
        if maze[nowH][nowW+1]=="#":
          maze[nowH][nowW+1]="1"
          heapq.heappush(que, [1,nowH,nowW+1])
        elif maze[nowH][nowW+1]==".":
          maze[nowH][nowW+1]="0"
          heapq.heappush(que, [0,nowH,nowW+1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
suma = 0
for i in range(N-1):
    for j in range(i+1,N):
        suma += (A[i]^A[j])%(10**9+7)
print(suma%(10**9+7))


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
suma = 0
maxa = max(A)
bin = format(maxa,'b')
for i in range(len(bin)):
    count1 = 0
    for j in range(N):
        if (A[j] >> i) & 1 == 1:
            count1 += 1
    suma = (suma+(N-count1)*count1*((2**i))%(10**9+7))%(10**9+7)
print(suma)
### BUGGY CODE ###

def resolve():
    import numpy as np
    N = int(input())
    D = sorted(list(map(int, input().split())))
    d = np.array(D)
    idx = len(D) // 2
    ans = 0
    for i in range(d[idx - 1], d[idx]+1):
        if len(d[d < i]) == len(d[d >= i]):
            ans += 1
    print(ans)

resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    D = sorted(list(map(int, input().split())))
    idx = len(D) // 2
    mid = D[idx]
    low = D[idx - 1]
    if mid == low:
        print(0)
        return

    print(mid - low)

resolve()
### BUGGY CODE ###

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


m = 0

for i in range(n-1):
    s = xor = a[i]
    for j in range(i+1, n):
        xor = xor ^ a[j]
        s += a[j]
        if xor == s:
            m += 1
        else:
            break

print(m+n)

### FIXED CODE ###

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

cur = a[0]
ans = 0
rp = 1

for lp in range(n):
    while rp < n and cur & a[rp] == 0:
        cur += a[rp]
        rp += 1
    ans += rp - lp
    cur -= a[lp]

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

H,W=map(int, input().split())
S = []
for i in range(H):
  S.append(input())

tate_value = [[0]*W for i in range(H)]
yoko_value = [[0]*W for i in range(H)]

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      yoko_value[i][j] = 0
    else:
      if j==0:
        left = 0
        right = W-1
        for k in range(0,W):
          if S[i][k] == '#':
            right = k-1
            break
        yoko_value[i][j] = right+1
      else:
        if S[i][j-1] == '.':
          yoko_value[i][j] = yoko_value[i][j-1]
        else:
          right = W-1
          for k in range(j,W):
            if S[i][k] == '#':
              right = k-1
              break
          yoko_value[i][j] = right-j+1

for j in range(W):
  for i in range(H):
    if S[i][j] == '#':
      tate_value[i][j] = 0
    else:
      if i==0:
        up = 0
        down = H-1
        for k in range(0,H):
          if S[k][j] == '#':
            down = k-1
            break
        tate_value[i][j] = down+1
      else:
        if S[i-1][j] == '.':
          tate_value[i][j] = tate_value[i-1][j]
        else:
          down = H-1
          for k in range(i,H):
            if S[k][j] == '#':
              down = k-1
              break
          tate_value[i][j] = down-i+1
max = 0
for i in range(H):
  for j in range(W):
    temp = yoko_value[i][j] + tate_value[i][j]-1
    if temp>max:
      max = temp
      
print(max)

### FIXED CODE ###

H,W=map(int, input().split())
S = []
for i in range(H):
  S.append(input())

tate_value = [[0]*W for i in range(H)]
yoko_value = [[0]*W for i in range(H)]

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      yoko_value[i][j] = 0
    else:
      if j==0:
        left = 0
        right = W-1
        for k in range(0,W):
          if S[i][k] == '#':
            right = k-1
            break
        yoko_value[i][j] = right+1
      else:
        if S[i][j-1] == '.':
          yoko_value[i][j] = yoko_value[i][j-1]
        else:
          right = W-1
          for k in range(j,W):
            if S[i][k] == '#':
              right = k-1
              break
          yoko_value[i][j] = right-j+1

for j in range(W):
  for i in range(H):
    if S[i][j] == '#':
      tate_value[i][j] = 0
    else:
      if i==0:
        up = 0
        down = H-1
        for k in range(0,H):
          if S[k][j] == '#':
            down = k-1
            break
        tate_value[i][j] = down+1
      else:
        if S[i-1][j] == '.':
          tate_value[i][j] = tate_value[i-1][j]
        else:
          down = H-1
          for k in range(i,H):
            if S[k][j] == '#':
              down = k-1
              break
          tate_value[i][j] = down-i+1
          
max = 0
for i in range(H):
  for j in range(W):
    temp = yoko_value[i][j] + tate_value[i][j]-1
    if temp>max:
      max = temp
      
print(max)
### BUGGY CODE ###

from bisect import bisect_right
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


n, t = map(int, input().split())

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

INF = 10**10
# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[INF for _ in range(n+1)] for __ in range(30)]
dp[0][0] = 0

m = min(n+1, 30)

for j in range(m):
    for i in range(n):
        dp[j][i+1] = min(dp[j][i], dp[j-1][i] + 1 +
                         shop[i][0]*(dp[j-1][i]+1) + shop[i][1])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(m):
    if t - dp[i][n] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[i][n]) + i)

print(ans)


### FIXED CODE ###

from bisect import bisect_right
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


n, t = map(int, input().split())

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

INF = 10**10
# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[INF for _ in range(31)] for __ in range(n+1)]
dp[0][0] = 0

m = min(n+1, 30)

for i in range(n):
    for j in range(m):
        if (shop[i][0]+1)*(dp[i][j]+1) + shop[i][1] > t:
            dp[i+1][j+1] = dp[i][j+1]
        else:
            dp[i+1][j+1] = min(dp[i][j+1], (shop[i][0]+1)
                               * (dp[i][j]+1) + shop[i][1])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(m):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)