CodeEff/ECCO huggingface dataset:
# Original solution
def main():
  from collections import defaultdict
  from heapq import heappush,heappop,heapify
  from bisect import bisect_left
  B=bisect_left
  inf=2**31-1
  n,m,*t=list(map(int,open(0).read().split()))
  if not t:
    print((-1))
    exit()
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z=sorted(set(z))
  edge=[[]for _ in z]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=B(z,a),B(z,b),B(z,a+n*c),B(z,b+n*c)
    if b==n:
      l.append(y)
      d[y]=inf
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[True]*len(z)
  used[0]=False
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print(([a,-1][a==inf]))
if __name__=='__main__':
  main()

# Optimized solution
def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=list(map(int,open(0).read().split()))
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z={i:v for v,i in enumerate(sorted(set(z)))}
  try:
    z[1]
  except:
    print((-1))
    exit()
  edge=[[]for _ in range(len(z))]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
    if b==n:
      l.append(y)
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[False]+[True]*~-len(z)
  d=[0]+[inf]*~-len(z)
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print(([a,-1][a==inf]))
if __name__=='__main__':
  main()
# Original solution
def resolve():
    def Dijkstra(s, g):
        import heapq
        d = {}
        d[s] = 0
        queue = []
        for q in edge[s]:
            heapq.heappush(queue, q)
        while queue:
            dist, point = heapq.heappop(queue)
            if point in d:
                continue
            d[point] = dist
            if point == g:
                return dist
            for nextdist, nextp in edge[point]:
                if not nextp in d:
                    heapq.heappush(queue, (dist + nextdist, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = list(map(int, input().split()))
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = list(map(int, input().split()))
        p, q = p - 1, q - 1
        edge[(p, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
    print((Dijkstra((0, -1), (n - 1, -1))))


if __name__ == '__main__':
    resolve()


# Optimized solution
def resolve():
    def Dijkstra(s, g):
        import heapq
        d = {}
        d[s] = 0
        queue = []
        for q in edge[s]:
            heapq.heappush(queue, q)
        while queue:
            dist, point = heapq.heappop(queue)
            q = [point]
            while q:
                point = q.pop()
                if point in d:
                    continue
                d[point] = dist
                if point == g:
                    return dist
                for nextdist, nextp in edge[point]:
                    if not nextp in d:
                        if nextdist == 0:
                            q.append(nextp)
                        else:
                            heapq.heappush(queue, (dist + nextdist, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = list(map(int, input().split()))
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = list(map(int, input().split()))
        p, q = p - 1, q - 1
        edge[(p, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
    print((Dijkstra((0, -1), (n - 1, -1))))


if __name__ == '__main__':
    resolve()
# Original solution
def resolve():
    def Dijkstra(s, g):
        import heapq
        d = {s}
        queue = []
        for q in edge[s]:
            heapq.heappush(queue, q)
        while queue:
            dist, point = heapq.heappop(queue)
            q = [point]
            while q:
                point = q.pop()
                if point in d:
                    continue
                d.add(point)
                if point == g:
                    return dist
                for nextdist, nextp in edge[point]:
                    if not nextp in d:
                        if nextdist:
                            heapq.heappush(queue, (dist + 1, nextp))
                        else:
                            q.append(nextp)
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = list(map(int, input().split()))
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = list(map(int, input().split()))
        p, q = p - 1, q - 1
        edge[(p, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
    print((Dijkstra((0, -1), (n - 1, -1))))


if __name__ == '__main__':
    resolve()


# Optimized solution
def resolve():
    def Dijkstra(s, g):
        from collections import deque
        d = {s}
        queue = deque()
        for q in edge[s]:
            queue.append(q)
        while queue:
            dist, point = queue.popleft()
            if point in d:
                continue
            d.add(point)
            if point == g:
                return dist
            for nextdist, nextp in edge[point]:
                if not nextp in d:
                    if nextdist:
                        queue.append((dist + 1, nextp))
                    else:
                        queue.appendleft((dist, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = list(map(int, input().split()))
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = list(map(int, input().split()))
        p, q = p - 1, q - 1
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
    print((Dijkstra((0, -1), (n - 1, -1))))


if __name__ == '__main__':
    resolve()
# Original solution
from collections import deque

n, m = list(map(int, input().split()))
edges = [[] for i in range(n)]
for i in range(m):
    p, q, c = list(map(int, input().split()))
    p, q, c = p-1, q-1, c-1
    edges[p].append((q, c))
    edges[q].append((p, c))

que = deque()
cost = [float("inf")]*n
colr = [-1]*n
# now, prev,prev_color, cost
que.append((0, -1, -1, 0))

while que:
    now, prev, prev_color, cost_now = que.popleft()
    if cost[now] < cost_now or (cost[now] == cost_now and colr[now] == prev_color):
        continue
    cost[now] = cost_now
    colr[now] = prev_color
    for to, color in edges[now]:
        if to == prev:
            continue
        if cost_now+int(color!=prev_color) <= cost[to]:
            que.append((to, now, color, cost_now+int(color!=prev_color)))
if cost[-1] == float("inf"):
    print((-1))
else:
    print((cost[-1]))

# Optimized solution
# https://juppy.hatenablog.com/entry/2019/04/10/ARC061_-_E_%E3%81%99%E3%81%AC%E3%81%91%E5%90%9B%E3%81%AE%E5%9C%B0%E4%B8%8B%E9%89%84%E6%97%85%E8%A1%8C_-_Python_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder
# 参考にさせていただきました。

from collections import deque, defaultdict

chg = 10**6
n, m = list(map(int, input().split()))
edges = defaultdict(set)
# m=0のためにdefaultdictにしておくべき
visited = defaultdict(set)
for i in range(m):
    p, q, c = list(map(int, input().split()))
    edges[p+c*chg].add(q+c*chg)
    edges[q+c*chg].add(p+c*chg)
    edges[p].add(p+c*chg)
    edges[q].add(q+c*chg)
    edges[p+c*chg].add(p)
    edges[q+c*chg].add(q)
    visited[p] = False
    visited[q] = False
    visited[p+c*chg] = False
    visited[q+c*chg] = False

ans = float("inf")
que = deque()
# now, dist
que.append((1, 0))
# 今求めるのはendの距離だけなので、dist配列はいらない
# さらに、距離は0/1なのでheapで辺を管理する必要もなく、0なら最短確定なので先に、1ならその時点での最長なので後ろにすれば良い
while que:
    now, dist = que.popleft()
    if visited[now]:
        continue
    visited[now] = True
    if now == n:
        ans = dist
        break
    for to in edges[now]:
        # 駅→ホーム
        if now < chg and to > chg:
            que.append((to, dist+1))
        else:
            que.appendleft((to, dist))
if ans == float("inf"):
    print((-1))
else:
    print(ans)
# Original solution
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = list(map(int, read().split()))

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
INF = 1<<30
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue

    for tl in g[vl]:
        cost = (vl&mask==0 or tl&mask==0)
        ndv = cost + dv
        if (tl not in res or res[tl] > ndv):
            res[tl] = ndv
            if cost: q.appendleft((tl,ndv))
            else: q.append((tl,ndv))
            

if (n-1)<<20 in res:
    print((res[(n-1)<<20]//2))
else:
    print((-1))






# Optimized solution
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*pqc = list(map(int, read().split()))

g = {}
M = iter(pqc)

for p,q,c in zip(M,M,M):
    pc = ((p-1)<<20)+c
    qc = ((q-1)<<20)+c
    pp = (p-1)<<20
    qq = (q-1)<<20
    
    if pc not in g: g[pc] = []
    if qc not in g: g[qc] = []
    if pp not in g: g[pp] = []
    if qq not in g: g[qq] = []
    
    g[pc].append(qc)
    g[pc].append(pp)

    g[qc].append(pc)
    g[qc].append(qq)

    g[pp].append(pc)
    g[qq].append(qc)

if 0 not in g: g[0] = []

from collections import deque
q = deque([(0,0)])
res = {0:0}

mask = (1<<20)-1
while q:
    vl,dv = q.popleft()
    if res[vl] < dv: continue
    if (vl>>20) == n-1:
        res[(n-1)<<20] = dv+1
        break
    for tl in g[vl]:
        ndv = dv + (vl&mask==0 or tl&mask==0)
        if tl not in res or res[tl] > ndv:
            res[tl] = ndv
            if vl&mask==0 or tl&mask==0:
                q.append((tl,ndv))
            else:
                q.appendleft((tl,ndv))

if (n-1)<<20 in res:
    print((res[(n-1)<<20]//2))
else:
    print((-1))
# Original solution
from collections import deque, defaultdict
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        adj[p].append((q, c))
        adj[q].append((p, c))

    deq = deque()
    cost = [10 ** 7] * (N+1)
    seen = [defaultdict(int) for _ in range(N+1)]
    prev = defaultdict(list)
    deq.append(1)
    cost[1] = 0
    flag = [1] * (N+1)
    while deq:
        v = deq.pop()
        flag[v] = 1
        for uc in adj[v]:
            u, c = uc
            # print(v, u, c)
            # print(deq, prev, cost)
            # print(seen[4])
            if c in prev[v] and seen[u][c] == 0:
                if cost[u] == cost[v]:
                    prev[u].append(c)
                    if flag[u]:
                        deq.append(u)
                        flag[u] = 0
                elif cost[u] > cost[v]:
                    cost[u] = cost[v]
                    deq.append(u)
                    flag[u] = 0
                    prev[u] = [c]
                seen[v][c] = 1
            else:
                if cost[u] > cost[v] + 1:
                    cost[u] = cost[v] + 1
                    deq.appendleft(u)
                    flag[u] = 0
                    prev[u] = [c]
                elif cost[u] == cost[v] + 1:
                    prev[u].append(c)

    print(cost[N]) if cost[N] < 10 ** 7 else print(-1)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N, M = list(map(int, input().split()))
    adj = [[] for _ in range(N+1)]
    c2v = {}
    v = N+1
    for _ in range(M):
        p, q, c = list(map(int, input().split()))
        P = p*(10**7) + c
        Q = q*(10**7) + c
        if P not in c2v:
            c2v[P] = v
            adj[p].append((v, 1))
            adj.append([(p, 1)])
            v += 1
        if Q not in c2v:
            c2v[Q] = v
            adj[q].append((v, 1))
            adj.append([(q, 1)])
            v += 1
        adj[c2v[P]].append((c2v[Q], 0))
        adj[c2v[Q]].append((c2v[P], 0))

    que = deque()
    que.append(1)
    seen = [-1] * len(adj)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + cost
                if cost:
                    que.append(u)
                else:
                    que.appendleft(u)
    print((seen[N] // 2))


if __name__ == '__main__':
    main()
# Original solution
import bisect

N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append(((b + 1) / a, a, b))
a0.sort()

nab.sort()

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

dp = [0] + [float('inf')] * 29
for index, (_, a, b) in enumerate(nab):
    # print(a, b)
    ndp = [0] + [float('inf')] * 29
    for count in range(1, 29):
        ndp[count] = min(dp[count],
                         dp[count - 1] + 1 + (dp[count - 1] + 1) * a + b)
    dp = ndp

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)


# Optimized solution
import bisect

N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append(((b + 1) / a, a, b))
a0.sort()

nab.sort()

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

INF = 1 << 32
dp = [0] + [INF] * 29
for index, (_, a, b) in enumerate(nab):
    # print(a, b)
    ndp = [0] + [INF] * 29
    for count in range(1, 29):
        ndp[count] = min(dp[count],
                         dp[count - 1] + 1 + (dp[count - 1] + 1) * a + b)
    dp = ndp

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)
# Original solution
def main():
    # input
    N, T = list(map(int, input().split()))
    a, b = [], []
    a0_b = []
    for i in range(N):
        a_in, b_in = list(map(int, input().split()))
        if a_in == 0:
            a0_b.append(b_in)
        else:
            a.append(a_in)
            b.append(b_in)
    L = len(a)

    # sort
    ab_ratio = [a[i] / (b[i] + 1) for i in range(L)]
    key = sorted(list(range(L)), key=lambda x: -ab_ratio[x])
    a = [a[i] for i in key]
    b = [b[i] for i in key]
    a0_b.sort()

    # --- case a >= 1 --- #
    # dp[for i shops][passed j shops] := min time
    # j:29 for T < 10^9
    J_MAX = min(L + 1, 29)
    dp = [[float('inf') for _ in range(J_MAX)] for _ in range(L + 1)]
    dp[0][0] = 0
    for i in range(L):
        for j in range(J_MAX):
            if j > 0:
                dt = 1 + a[i] * (dp[i][j - 1] + 1) + b[i]
                if dp[i][j - 1] + dt <= T:
                    dp[i + 1][j] = min(dp[i][j], dp[i][j - 1] + dt)
                else:
                    dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = dp[i][j]

    # --- case a = 0 --- #
    ans = 0
    for i in range(J_MAX):
        if dp[L][i] == float('inf'):
            break
        else:
            time_cnt = dp[L][i]
            shop_cnt = i
            for t_b in a0_b:
                if time_cnt + 1 + t_b <= T:
                    time_cnt += 1 + t_b
                    shop_cnt += 1
            if ans < shop_cnt:
                ans = shop_cnt

    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
import sys
input = sys.stdin.readline


def main():
    # input
    N, T = list(map(int, input().split()))
    a, b = [], []
    a0_b = []
    for i in range(N):
        a_in, b_in = list(map(int, input().split()))
        if a_in == 0:
            a0_b.append(b_in)
        else:
            a.append(a_in)
            b.append(b_in)
    L = len(a)

    # sort
    ab_ratio = [a[i] / (b[i] + 1) for i in range(L)]
    key = sorted(list(range(L)), key=lambda x: -ab_ratio[x])
    a = [a[i] for i in key]
    b = [b[i] for i in key]
    a0_b.sort()

    # --- case a >= 1 --- #
    # dp[for i shops][passed j shops] := min time
    # j:29 for T < 10^9
    J_MAX = min(L + 1, 29)
    dp = [[float('inf') for _ in range(J_MAX)] for _ in range(L + 1)]
    dp[0][0] = 0
    for i in range(L):
        for j in range(J_MAX):
            if j > 0:
                dt = 1 + a[i] * (dp[i][j - 1] + 1) + b[i]
                if dp[i][j - 1] + dt <= T:
                    dp[i + 1][j] = min(dp[i][j], dp[i][j - 1] + dt)
                else:
                    dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = dp[i][j]

    # --- case a = 0 --- #
    ans = 0
    for i in range(J_MAX):
        if dp[L][i] == float('inf'):
            break
        else:
            time_cnt = dp[L][i]
            shop_cnt = i
            for t_b in a0_b:
                if time_cnt + 1 + t_b <= T:
                    time_cnt += 1 + t_b
                    shop_cnt += 1
            if ans < shop_cnt:
                ans = shop_cnt

    print(ans)


if __name__ == '__main__':
    main()
# Original solution
#!/usr/bin/env pypy3

import sys
import math
import itertools
import bisect

INF = int(1e18)
T_MAX = int(1e9)

def main():
    N, T = list(map(int, sys.stdin.readline().split()))
    shops = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

    nzshops = [(a, b) for a, b in shops if a > 0]
    zshops  = [(a, b) for a, b in shops if a == 0]

    nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    zshops.sort()

    dp = [[0] + [INF] * int(math.log(T_MAX, 2)) for _ in range(len(nzshops) + 1)]
    for i in range(1, len(dp)):
        for c in range(1, len(dp[i])):
            a, b = nzshops[i - 1]
            t = dp[i - 1][c - 1] + 1
            dp[i][c] = min(dp[i - 1][c], t + t * a + b)

    rs = list(itertools.accumulate(1 + b for _, b in zshops))
    ans = max(c + bisect.bisect(rs, T - dp[-1][c])
            for c in range(len(dp[-1])) if dp[-1][c] <= T)

    print(ans)

if __name__ == '__main__':
    main()

# Optimized solution
#!/usr/bin/env pypy3

import sys
import math
import itertools
import bisect

INF = int(1e18)

def main():
    n, t = list(map(int, sys.stdin.readline().split()))

    nzshops = []
    zshops = []
    for _ in range(n):
        a, b = list(map(int, sys.stdin.readline().split()))
        (zshops if a == 0 else nzshops).append((a, b))

    nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    zshops.sort()

    dp = [0]
    for i in range(len(nzshops)):
        dp_ = dp + [INF]
        for c in range(1, len(dp_)):
            a, b = nzshops[i]
            x = dp[c - 1] + 1
            dp_[c] = min(dp_[c], x + x * a + b)
        dp = [x for x in dp_ if x <= t]

    rs = list(itertools.accumulate(1 + b for _, b in zshops))
    ans = max(c + bisect.bisect(rs, t - dp[c])
            for c in range(len(dp)) if dp[c] <= t)

    print(ans)

if __name__ == '__main__':
    main()
# Original solution
#!/usr/bin/env pypy3

import sys
import math
import itertools
import bisect

INF = int(1e18)

def main():
    n, t = list(map(int, sys.stdin.readline().split()))

    nzshops = []
    zshops = []
    for _ in range(n):
        a, b = list(map(int, sys.stdin.readline().split()))
        (zshops if a == 0 else nzshops).append((a, b))

    nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    zshops.sort()

    dp = [0]
    for i in range(len(nzshops)):
        dp_ = dp + [INF]
        for c in range(1, len(dp_)):
            a, b = nzshops[i]
            x = dp[c - 1] + 1
            dp_[c] = min(dp_[c], x + x * a + b)
        dp = [x for x in dp_ if x <= t]

    rs = list(itertools.accumulate(1 + b for _, b in zshops))
    ans = max(c + bisect.bisect(rs, t - dp[c])
            for c in range(len(dp)) if dp[c] <= t)

    print(ans)

if __name__ == '__main__':
    main()

# Optimized solution
#!/usr/bin/env pypy3

import sys
import math
import itertools
import bisect

INF = int(1e18)

n, t = list(map(int, sys.stdin.readline().split()))

nzshops = []
zshops = []
for _ in range(n):
    a, b = list(map(int, sys.stdin.readline().split()))
    (zshops if a == 0 else nzshops).append((a, b))

nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
zshops.sort()

dp = [0]
for i in range(len(nzshops)):
    a, b = nzshops[i]
    dp.append(INF)
    for c in range(len(dp) - 1, 0, -1):
        x = dp[c - 1] + 1
        dp[c] = min(dp[c], x + x * a + b)
    dp = [x for x in dp if x <= t]

rs = list(itertools.accumulate(1 + b for _, b in zshops))
ans = max(c + bisect.bisect(rs, t - dp[c])
        for c in range(len(dp)) if dp[c] <= t)

print(ans)