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

import sys
from itertools import accumulate
input = sys.stdin.readline
def main():
    N, K = map( int ,input().split())
    TK = K*2
    B = [[0]*(K*2) for _ in range(TK)]
    for _ in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "B":
            B[x%TK][y%TK] += 1
        else:
            B[x%TK][(y+K)%TK] += 1
    C = [[0]*(TK+1)] + [[0] + list( accumulate(B[i])) for i in range(TK)]
    for i in range(TK):
        for j in range(TK+1):
            C[i+1][j] += C[i][j]
    def get(i1, j1, i2, j2):
        return C[i2][j2] - C[i1][j2] - C[i2][j1] + C[i1][j1]
    ans = 0
    for i in range(K+1):
        for j in range(K+1):
            if ans < get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK):
                ans = get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK)
            if ans < get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK):
                ans = get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK)
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from itertools import accumulate
input = sys.stdin.readline
def main():
    N, K = map( int ,input().split())
    TK = K*2
    B = [[0]*(K*2) for _ in range(TK)]
    for _ in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "B":
            B[x%TK][y%TK] += 1
        else:
            B[x%TK][(y+K)%TK] += 1
    C = [[0]*(TK+1)] + [[0] + list( accumulate(B[i])) for i in range(TK)]
    for i in range(TK):
        for j in range(TK+1):
            C[i+1][j] += C[i][j]
    def get(i1, j1, i2, j2):
        return C[i2][j2] - C[i1][j2] - C[i2][j1] + C[i1][j1]
    ans = 0
    for i in range(K+1):
        for j in range(K+1):
            if ans < get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK):
                ans = get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK)
            if ans < get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK):
                ans = get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK)
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]

A.sort(reverse=True)
B.sort(reverse=True)

if len(set(A))!=len(A) or len(set(B))!=len(B):
    print(0)
    sys.exit()

ans = 1
rows, columna = 0,0
mod = 10**9+7
for x in range(N*M, 0, -1):
    in_A = x in A
    in_B = x in B

    if in_A and in_B:
        rows += 1
        columna += 1

    elif in_A:
        rows += 1
        ans = ans * (columna)

    elif in_B:
        columna += 1
        ans = ans *(rows)

    else:
        ans = ans * (rows * columna -(N*M-x))

    ans %= mod

print(ans%mod)


### FIXED CODE ###

def solve():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = set(map(int, input().split()))
    B = set(map(int, input().split()))
    
    row, columun = 0, 0
    ans = 1
    for i in range(N * M, 0, -1):
        in_A = i in A
        in_B = i in B
        if in_A and in_B:
            row += 1
            columun += 1
        elif in_A:
            row += 1
            ans *= columun
        elif in_B:
            columun += 1
            ans *= row
        else:
            ans *= row * columun - (N * M - i)
        ans %= MOD
    print(ans)


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

N,M = map(int, input().split())
PY = [list(map(int,input().split())) for _ in range(M)]
PY_original = tuple(PY)
N_counter = [0] * N
M_counter = [0] * M

PY.sort(key=lambda val: val[1])
i = 0

for P,Y in PY:
    N_counter[P-1] += 1
    M_counter[i] = N_counter[P-1]
    i += 1

for i in PY_original:
    ans = str(i[0]).zfill(6)+str(M_counter[PY.index(i)]).zfill(6)
    print(ans)

### FIXED CODE ###

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

PY = [[i] for i in range(1,M+1)]

for i in range(M):
    temp1, temp2 = map(int, input().split())
    PY[i].append(temp1)
    PY[i].append(temp2)


PY.sort(key=lambda val: val[2])
# print(PY)
PY.sort(key=lambda val: val[1])
# print(PY)
city = 0

for i, value in enumerate(PY):
    if value[1] != city:
        j = 0
    j += 1
    value.append(j)
    city = value[1]

PY.sort(key=lambda val:val[0])

# print(PY)

for i in PY:
    ans = str(i[1]).zfill(6)+str(i[3]).zfill(6)
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(len(a)-1):
    for j in range(i+1, len(a)):
        x += ((a[i]%(10**9+7))*(a[j]%(10**9+7)))%(10**9+7)
        x = x%(10**9+7)
print(x%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
m = sum(a)
for i in range(len(a)-1):
    m = (m-a[i])%(10**9+7)
    x += a[i]*m
    x = x%(10**9+7)
print(x%(10**9+7))
### BUGGY CODE ###

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
t = [[-1] * w for _ in range(h)]
cnt = [0] * 2005
ans = 0
for i in range(h):
    x = 1
    cnt[1] = 0
    for j in range(w):
        if s[i][j] == ".":
            t[i][j] = x
            cnt[x] += 1
        else:
            x += 1
            cnt[x] = 0
    for j in range(w):
        if not t[i][j] == -1:
            t[i][j] = cnt[t[i][j]]
for j in range(w):
    x = 1
    cnt[1] = 0
    for i in range(h):
        if s[i][j] == ".":
            s[i][j] = x
            cnt[x] += 1
        else:
            x += 1
            cnt[x] = 0
    for i in range(h):
        if not s[i][j] == "#":
            ans = max(ans, t[i][j] + cnt[s[i][j]] - 1)
print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
t = ["#"] * (w + 2)
s = [["#"] + list(input()) + ["#"] for _ in range(h)]
s.append(t)
s.insert(0, t)
dp_n = [[0] * (w + 2) for _ in range(h + 2)]
dp_s = [[0] * (w + 2) for _ in range(h + 2)]
dp_e = [[0] * (w + 2) for _ in range(h + 2)]
dp_w = [[0] * (w + 2) for _ in range(h + 2)]
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if s[i][j] == ".":
            dp_n[i][j] += dp_n[i - 1][j] + 1
        if s[h + 1 - i][j] == ".":
            dp_s[h + 1 - i][j] += dp_s[h + 2 - i][j] + 1
for j in range(1, w + 1):
    for i in range(1, h + 1):
        if s[i][j] == ".":
            dp_w[i][j] += dp_w[i][j - 1] + 1
        if s[i][w + 1 - j] == ".":
            dp_e[i][w + 1 - j] += dp_e[i][w + 2 - j] + 1
ans = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        c = dp_n[i][j] + dp_s[i][j] + dp_e[i][j] + dp_w[i][j] - 3
        if c > ans:
            ans = c
print(ans)
### BUGGY CODE ###

k,s=[int(i) for i in input().split()]
count=0
for y in range(k+1):
 for x in range(k+1):
   if x + y <= s + k and s>=x+y and s<=k+x+y:
      count=count+1
print(count)


### FIXED CODE ###

k,s=[int(i) for i in input().split()]
count=0
for y in range(k+1):
 for x in range(k+1):
   if x + y <= s + k and s>=x+y and s<=k+x+y:
      count=count+1
print(count)
### BUGGY CODE ###

N = int(input())
aA=list(set(int(_) for _ in input().split()))
N = len(aA)
def ggg(i,j):
    if i < j :
        i,j = j,i
    i %= j
    if i == 0:
        return j
    else:
        return ggg(j,i)

if len(aA) == 1:
    print(aA[0])
else:
    iMin = min(aA)
    iMax = max(aA)
    if iMin  == 1:
        print(1)
    else:
        if max(i % iMin for i in aA) == 0:
            print(iMin)
            exit()
        else:
            iM = iMax
            for i in range(N):
                iA = aA[i]
                for j in range(i+1,N):
                    iMt = ggg(iA,aA[j])
                    if 0 < iMt and iMt < iM:
                        iM = iMt
                    if iM == 1:
                        print(1)
                        exit()
            print(iM)


### FIXED CODE ###

#gcdか....
def fgcd(a,b):
    while b:
        a,b = b,a%b
    return a

N = int(input())
aA = sorted(set(int(_) for _ in input().split()))
b = aA[0]
for a in aA[1:]:
    b = fgcd(a,b)
print(b)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

ans = 0
for i in range(N):
    h_i = A[i]
    for j in range(h_i + i, N):
        if h_i + A[j] == j - i:
            ans += 1
print(ans)

### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())

A = LI()

A_ii = copy.deepcopy(A)
for i in range(N):
    A_ii[i] += i
dic_A_ii = collections.Counter(A_ii)

A_jj = copy.deepcopy(A)

for j in range(N):
    A_jj[j] = -1 * A_jj[j] + j

ans = 0
dic_A_jj = collections.Counter(A_jj)
# print(dic_A_ii)
# print(dic_A_jj)

for ii_key in dic_A_ii.keys():
    ans += dic_A_jj[ii_key] * dic_A_ii[ii_key]

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

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

Swap=[None]*M
for i in range(M):
    Swap[i]=set(map(int,input().split()))

finish=M

for i in range(1,N+1):
    for j in range(finish):
        if i in Swap[j]:
            k=j
            break
    j+=1
    while j<finish:
        if i in Swap[j]:
            Swap[k]=Swap[k]|Swap[j]
            del Swap[j]
            finish-=1
            j-=1
        j+=1

Other=set(range(1,N+1))
for l in range(finish):
    Other=Other - Swap[l]

count=0

for i in range(finish):
    for j in Swap[i]:
        if P[j-1] in Swap[i]:
            count+=1
        

for m in Other:
    if P[m-1]==m:
        count+=1

print(count)
        


### FIXED CODE ###

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

Group=[i for i in range(N+1)]


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

for i in range(N):
    if find(P[i])==find(i+1):
        count+=1


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

N = int(input())
As = list(map(int, input().split()))
 
sum_humidai = 0
 
for person_idx, person_height in enumerate(As):
  
  if person_idx == 0:
    continue
    
  max_front_person = max(As[:person_idx])
  if max_front_person > person_height:
    humidai = max_front_person - person_height
    sum_humidai += humidai
 
print(sum_humidai)

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
 
sum_humidai = 0
max_front_person = 0
  
for person_idx, person_height in enumerate(As):
  
  if person_idx == 0:
    continue
    
  max_front_person = max(max_front_person, As[person_idx - 1])
  if max_front_person > person_height:
    humidai = max_front_person - person_height
    sum_humidai += humidai
 
print(sum_humidai)
### BUGGY CODE ###

n = int(input())
s = input()

dp = [[0 for _ in range(n)] for _ in range(n)]
all_patterns = dict()
max_val = 0
for i in range(n):
    for j in range(i,n):
        target = s[i:j+1]
        if target in all_patterns and len(target) > max_val and i>all_patterns[target][1]:
            max_val = len(target)
        else:
            all_patterns[target] = [i,j]

print(max_val)

### FIXED CODE ###

n = int(input())
s = input()

def z_algorithm(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A


length = n

ans = 0
for i in range(length):
    temp = z_algorithm(s[i:])
    for j in range(len(temp)):
        if min(temp[j],j) > ans:
            ans = min(temp[j],j)
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
inf=100000000000000000000
fastinput=sys.stdin.readline
N=int(fastinput())
path=[[0]*N for hoge in range(N)]
for fuga in range(N-1):
    a,b,c=[int(hoge) for hoge in fastinput().split()]
    path[a-1][b-1]=c
    path[b-1][a-1]=c
Q,K=[int(hoge) for hoge in fastinput().split()]
stack=deque()
stack.append(K-1)
Kcost=[0]*N#あとあと初期化
went=[False]*N
went[K-1]=True
while stack:
    cur=stack.pop()
    curcost=Kcost[cur]
    for next,c in enumerate(path[cur]):
        if c and not went[next]:
            went[next]=True
            Kcost[next]=curcost+c
            stack.append(next)
for q in range(Q):
    x,y=[int(hoge) for hoge in fastinput().split()]
    print(Kcost[x-1]+Kcost[y-1])
    

### FIXED CODE ###

import sys
from collections import deque
inf=100000000000000000000
fastinput=sys.stdin.readline
N=int(fastinput())
path=[[] for hoge in range(N)]
for fuga in range(N-1):
    a,b,c=[int(hoge) for hoge in fastinput().split()]
    path[a-1].append([b-1,c])
    path[b-1].append([a-1,c])
Q,K=[int(hoge) for hoge in fastinput().split()]
stack=deque()
stack.append(K-1)
Kcost=[0]*N#あとあと初期化
went=[False]*N
went[K-1]=True
while stack:
    cur=stack.pop()
    curcost=Kcost[cur]
    for next,c in path[cur]:
        if c and not went[next]:
            went[next]=True
            Kcost[next]=curcost+c
            stack.append(next)
for q in range(Q):
    x,y=[int(hoge) for hoge in fastinput().split()]
    print(Kcost[x-1]+Kcost[y-1])
### BUGGY CODE ###

num_input = int(input())
input_arr = [int(x) for x in input().split()]

max_input = max(input_arr)
count = 0

for input_ in range(max_input):
    first_arr = [s for s in input_arr if input_ < s]
    second_arr = [s for s in input_arr if input_ >= s]
    if len(first_arr) == len(second_arr):
        count = count + 1
print(count)

### FIXED CODE ###

num_input = int(input())
input_arr = [int(x) for x in input().split()]

max_input = max(input_arr)
count = 0
second_arr =[]
first_arr = []
sorted_arr = sorted(input_arr)
ans = sorted_arr[int(num_input/2)] - sorted_arr[int(num_input/2)-1]
print(ans)
### BUGGY CODE ###

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

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

if mul > 10**18:
    print("-1")

else:
    print(mul)


### FIXED CODE ###

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

#print(A)

A.sort()
#print(A)

mul = 1
for i in range(N):
    if mul == 0:
        break
    elif mul > 10**18:
        mul = -1
        break
    else:
        mul *= A[i]
 
if mul > 10**18:
    print("-1")
else:
    print(mul)
### BUGGY CODE ###

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

for i in range(m):
    a.sort(reverse=True)
    a[0] = a[0]//2

print(sum(a))

### FIXED CODE ###

import heapq
n,m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x*(-1), a))

heapq.heapify(a)#ヒープ化
for i in range(m):
    tmp_max = heapq.heappop(a)
    heapq.heappush(a,tmp_max - tmp_max//2) #プッシュ
print(-sum(a))
### 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 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)

### 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 ###

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
mod = 10 ** 9 + 7

dp = [0] * (1 << n)
dp[0] = 1

for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k - 1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[-1])


### FIXED CODE ###

mod = 10**9+7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0]*(1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k-1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])
### BUGGY CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy

# from typing import Dict, List, Optional, Set, Tuple


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, _nb_vertices, nb_edges) -> int:
    succ = defaultdict(set)
    for s, d in values:
        succ[s].add(d)
    # all edges have a 0 length path starting at the edge
    dp = {s: True for s in succ}
    max_length_path = 0
    for length in range(1, nb_edges + 1):
        prev = dp.copy()
        dp = {s: False for s in succ}
        # vertices are indexed from 1
        for vertex in succ:
            for d in succ[vertex]:
                if prev.get(d - 1, False):
                    dp[vertex - 1] = True
                    max_length_path = length
                    break
    return max_length_path


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


def main():
    "Program wrapper."
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys
from collections import defaultdict

sys.setrecursionlimit(pow(2, 31) - 1)

# from typing import Dict, List, Optional, Set, Tuple

# def dfs(vertex: int, succ: Dict[int, List[int]], dp: Dict[int, int]) -> int:
def dfs(vertex, succ, dp):
    if vertex in dp:
        return dp[vertex]
    length = 0
    for s in succ[vertex]:
        length = max(length, 1 + dfs(s, succ, dp))
    dp[vertex] = length
    return length


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, _nb_vertices, _nb_edges) -> int:
    succ = defaultdict(list)
    for s, d in values:
        succ[s].append(d)
    # all edges have a 0 length path starting at the edge
    dp = defaultdict(lambda: -1)
    for vertex in frozenset(succ.keys()):
        if vertex in dp:
            dp[vertex] = max(dp[vertex], dfs(vertex, succ, dp))
        else:
            dp[vertex] = dfs(vertex, succ, dp)
    return max(dp.values())


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


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

import numpy as np
import sys

input = sys.stdin.readline

n, t = map(int, input().split())
shops = []
shopsA0 = []

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0:
        shopsA0.append(b+1)
    else:
        shops.append([a/(b + 1), a, b])

shops.sort(reverse=True)
shopsA0.sort()

DP = np.array([t+10]*30, dtype=np.int64)
DP[0] = 0

for _, a, b in shops:
    np.minimum(DP[1:], (DP[:-1]+1)*(a+1)+b, out=DP[1:])

cumA0 = np.cumsum(shopsA0, dtype=np.int64)

DP = DP[DP <= t]
DPA0 = np.searchsorted(cumA0, t-DP, side='right')
ans = np.arange(len(DP)) + DPA0
print(ans.max())


### FIXED CODE ###

def main():
    import itertools
    import sys
    buf = sys.stdin.buffer


    n, t = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    shops = []
    shopsA0 = [0]

    for a, b in zip(m, m):
        if a == 0:
            shopsA0.append(b + 1)
        else:
            shops.append([a / (b + 1), a, b])

    shopsA0.sort()
    shops.sort(reverse=True)


    DP = [t+10] * 30
    DP[0] = 0

    for _, a, b in shops:
        for num in range(28, -1, -1):
            candidate = (DP[num]+1) * (a+1) + b
            if candidate < DP[num+1]:
                DP[num+1] = candidate

    cumA0 = list(itertools.accumulate(shopsA0))

    ans = [0]
    count_A0 = len(cumA0) - 1
    for count, spend_time in enumerate(DP):
        residue = t - spend_time
        if residue < 0:
            break
        while count_A0 > 0 and cumA0[count_A0] > residue:
            count_A0 -= 1
        ans.append(count_A0 + count)
    print(max(ans))


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

N = int(input())
P = list(map(float, input().split()))
memo = [[0 for j in range(N+1)] for i in range(N)]

for i in range(N):
    if i == 0:
        memo[i][0] = 1 - P[i]
    else:
        memo[i][0] = memo[i-1][0] * (1 - P[i])
    for j in range(1, i+2):
        if i == 0:
            memo[i][j] = P[i]
        else:
            memo[i][j] = memo[i-1][j-1] * P[i]
            memo[i][j] += memo[i-1][j] * (1 - P[i])
            
print(sum(memo[-1][N//2+1:]))


### FIXED CODE ###

N = int(input())
P = list(map(float, input().split()))
memo = [[0 for j in range(N+1)] for i in range(N)]

memo[0][0] = 1 - P[0]
memo[0][1] = P[0]

for i in range(1, N):
    memo[i][0] = memo[i-1][0] * (1 - P[i])
    for j in range(1, i+2):
        memo[i][j] = memo[i-1][j-1] * P[i]
        memo[i][j] += memo[i-1][j] * (1 - P[i])
            
print(sum(memo[-1][N//2+1:]))
### BUGGY CODE ###

MOD=10**9+7
N,x=map(int,input().split())

a=list(map(int,input().split()))
a.sort()
a.reverse()
table=[[0 for i in range(N+1)] for j in range(x+1)]
for i in range(x+1):
	table[i][N]=i

for i in range(N-1,-1,-1):
	for x in range(x+1):
		table[x][i]=(table[x][i+1]*(N-1-i)+table[x%a[i]][i+1]) % MOD 

print(table[x][0])

### FIXED CODE ###

import math

def cul(i,x):
    if tmp[i][x]==-1:
        tmp[i][x]=( cul(i+1,x)*(N-1-i) + cul(i+1,x%a[i]) )%MOD
    return tmp[i][x]

MOD=10**9+7
N,x=map(int,input().split())

a=list(map(int,input().split()))
a.sort(reverse=True)
tmp= [[-1 for j in range(x+1)] for i in range(N)] + [[j for j in range(x+1)]]

print(cul(0,x))