Harryxun/stf_run huggingface dataset:
H,W,K = map(int,input().split())

dp = [[0]*(W+2) for _ in range(H+1)]
dp[0][1] = 1

    

for i in range(1,H+1):
    for x in range(2**(W-1)):           
        Alloc = [0]*9
        tmp = x
        for y in range(1,8):  
            Alloc[y] = tmp%2
            tmp //= 2 
        for y in range(0,9):
            if Alloc[y] == 1 and Alloc[y+1] == 1:
                break
        else:   
            for j in range(1,9):  
                if Alloc[j-1] == 1: 
                    dp[i][j] += dp[i-1][j-1]
                elif Alloc[j] == 1:
                    dp[i][j] += dp[i-1][j+1]
                else:
                    dp[i][j] += dp[i-1][j]
                dp[i][j] %= 1000000007

print(dp[H][K])


### FIXED CODE ###

H,W,K = map(int,input().split())

dp = [[0]*10 for _ in range(H+1)]   
dp[0][1] = 1

    

for i in range(1,H+1):
    for x in range(2**(W-1)):           
        Alloc = [0]*9
        tmp = x
        for y in range(1,8):  
            Alloc[y] = tmp%2
            tmp //= 2 
        for y in range(0,9):
            if Alloc[y] == 1 and Alloc[y+1] == 1:
                break
        else:   
            for j in range(1,9):  
                if Alloc[j-1] == 1: 
                    dp[i][j] += dp[i-1][j-1]
                elif Alloc[j] == 1:
                    dp[i][j] += dp[i-1][j+1]
                else:
                    dp[i][j] += dp[i-1][j]
                dp[i][j] %= 1000000007

print(dp[H][K])
N, M = map(int, input().split())
sc = []
for i in range(M):
    sp, cp = map(int, input().split())
    sc.append((sp, cp))

ans = 10000

for i in range(10 * N):
    num = str(i)
    flag = True
    for pair in sc:
        if (num[pair[0] - 1] != pair[1]) or len(num) < pair[0]:
            flag = False
            break
    if flag:
        ans = min(ans, i)

if ans == 10000:
    ans = -1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
sc = []
for i in range(M):
    sp, cp = map(int, input().split())
    sc.append((sp, cp))

ans = 10000

if N == 1:
    for i in range(10):
        num = str(i)
        flag = True
        for pair in sc:
            if (num[pair[0] - 1] != str(pair[1])):
                flag = False
                break
        if flag:
            ans = min(ans, i)
else:
    for i in range(10 ** (N - 1), 10 ** N):
        num = str(i)
        flag = True
        for pair in sc:
            if (num[pair[0] - 1] != str(pair[1])) or len(num) < pair[0]:
                flag = False
                break
        if flag:
            ans = min(ans, i)

if ans == 10000:
    ans = -1
print(ans)
S = inputs()
T = inputs()
print("Yes" if T.startswith(S) and len(T) == len(S) + 1 else "No", flush=True)

### FIXED CODE ###

S = input()
T = input()
print("Yes" if T.startswith(S) and len(T) == len(S) + 1 else "No", flush=True)
N = int(input())
A = list(map(int, input().split()))

import collections
dic=dict(collections.Counter(A))
li=list(dic.values())

ho=list(dic.keys)
x=ho[0]
y=ho[1]
z=ho[2]

ans='No'

if len(li)==3:
    if N%3 == 0:
        if li[0]== N//3 and li[1]==N//3 and x^y^z == 0:
            ans='Yes'           
elif len(li)==2:
    if N%3 == 0:
        if li[0]== 2*N//3 or li[1]==2*N//3:
            ans='Yes'
elif len(li)==1:
        if list(dic.keys())[0]==0:
            ans='Yes'

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter

def main():
    N = int(input())
    a = list(map(int, input().split()))
    l = Counter(a)
    if len(l)==1 and 0 in l:
        print('Yes')
        exit()
    if N%3==0 and len(l)==2 and 0 in l and l[0] == N//3:
        print('Yes')
        exit()
    if N%3==0 and len(l)==3:
        x,y,z = l.keys()
        if l[x] == l[y] == N//3 and x^y^z == 0:
            print('Yes')
            exit()
    print('No')

    

if __name__ == '__main__':
    main()
a, b c, d = [int(i) for i in input().split()]

if (a-c) <= d:
    print('Yes')
elif (a-b) <= d and (b-c) <= d:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

a, b, c, d = [int(i) for i in input().split()]

if abs(a-c) <= d:
    print('Yes')
elif abs(a-b) <= d and abs(b-c) <= d:
    print('Yes')
else:
    print('No')
import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = collections.Counter(ZZ())
    e = collections.defaultdict(list)
    l = [False] * (10 ** 6 + 5)

    def yakusu(num):
        ret = []
        lim = (num ** 0.5) + 5
        for i in range(1, lim):
            if i * i > num: break
            if num%i != 0: continue
            ret.append(i)
            if i != num//i: ret.append(num//i)
        return ret

    if 1 in A.keys():
        if A[1] == 1: print(1)
        elif A[1] >= 2: print(0)
        return

    ans = 0
    for n in A.keys():
        l[n] = True
        e[n] = yakusu(n)

    for n in A.keys():
        if A[n] >= 2: continue
        if len(e[n]) == 2:
            ans += 1
            continue
        for p in e[n]:
            if p in {1, n}: continue
            if l[p]: break
        else: ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = sorted(ZZ())
    cA = collections.Counter(A)
    MAX_A = 10 ** 6
    is_ok = [True] * (MAX_A + 1)

    if 1 in cA.keys():
        if cA[1] == 1: print(1)
        elif cA[1] >= 2: print(0)
        return

    for a in cA.keys():
        if not is_ok[a]: continue
        if cA[a] >= 2: is_ok[a] = False
        for i in range(2, MAX_A + 1):
            if a * i > MAX_A: break
            is_ok[a * i] = False

    ans = 0
    for a in cA.keys():
        if is_ok[a]: ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()
import math

N = input()

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

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

l = 1
for i in A:
    l = lcm(l, i)

ans = 0
for i in A:
    ans += l // i

print(ans%1000000007)

### FIXED CODE ###

MOD = 1000000007

def lcm(x, y):
    return (x * y) // gcd(x, y)

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x%y)

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

l = 1
for i in A:
    l = lcm(l, i)

l %= MOD

ans = 0
for i in A:
    ans += l*pow(i, MOD-2, MOD)
    ans %= MOD

print(ans)
import sys 

N, M = list(map(int, input().split()))
a_list = list()
b_list = list()
c_list = list()

for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
    c_list.append(-c)

inf = sys.maxsize
dist = [inf for _ in range(N)]
dist[0] = 0

for _ in range(N-1):
    for i in range(M):
        if dist[a[i]-1] == inf:
            continue
        if dist[b[i]-1] > dist[a[i]-1] + c[i]:
            dist[b[i]-1] = dist[a[i]-1] + c[i]

ans = dist[N-1]
negative = [False for _ in range(N)]

for _ in range(N):
    for i in range(M):
        if dist[a[i]-1] == inf:
            continue
        if dist[b[i]-1] > dist[a[i]-1] + c[i]:
            dist[b[i]-1] = dist[a[i]-1] + c[i]
            negative[b[i]-1] = True
        if negative[a[i]-1]:
            negative[b[i]-1] = True

if nagative[N-1]:
    print('inf')
else:
    print(str(-ans))



### FIXED CODE ###

import sys 

N, M = list(map(int, input().split()))
a_list = list()
b_list = list()
c_list = list()

for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
    c_list.append(-c)

inf = sys.maxsize
dist = [inf] * N
dist[0] = 0

for loop in range(N):
    for i in range(M):
        if dist[a_list[i]-1] == inf:
            continue
        if dist[b_list[i]-1] > dist[a_list[i]-1] + c_list[i]:
            dist[b_list[i]-1] = dist[a_list[i]-1] + c_list[i]
            if loop == N - 1 and b_list[i] == N:
                print('inf')
                sys.exit()

print(-dist[N-1])
s = input()
res = 0
for i in len(s):
  if s[i] == "1":
    res+= 1
print(res)

### FIXED CODE ###

s=input()
count = 0
if s[0] == "1":
    count = count + 1
if s[1] == "1":
    count = count + 1
if s[2] == "1":
    count = count + 1
print(count)
N, A, B = map(int, input().split())
set_bule = //(A+B) * A
other = N - N//(A+B) * (A+B)
if 0 <= other <= A:
    hashi_ bule = other
else :
    hashi_bule = A
print(set_bule + hashi_bule) 

### FIXED CODE ###

N, A, B = map(int, input().split())
set_bule = N//(A+B) * A
other = N - N//(A+B) * (A+B)
hashi_bule=0
if 0 <= other <= A:
    hashi_bule = other
else :
    hashi_bule = A
print(set_bule + hashi_bule)
n = int(input())
XYH = [list(map(int,input().split())) for _ in range(n)]
flag = False
for i in range(101):
    for j in range(101):
        tempH = abs(XYH[0][0] - i) + abs(XYH[0][1] - j) + XYH[0][2] 
        for x,y,h in XYH[1:]:
            if abs(x - i) + abs(y - j) + h != tempH:
                flag = False
                break
            else:
                flag = True
        if flag:
            ans = [i,j,tempH]
            break
    if flag:
        break

print(*ans,sep = " ")            
                
            

### FIXED CODE ###

n = int(input())
XYH = []

for _ in range(n):
    x,y,h = map(int,input().split())
    if h != 0:
        XYH.append([x,y,h])

flag = False
ans = XYH[0]
for i in range(101):
    for j in range(101):
        tempH = abs(XYH[0][0] - i) + abs(XYH[0][1] - j) + XYH[0][2]
        for x,y,h in XYH[1:]:
            if abs(x - i) + abs(y - j) + h != tempH:
                flag = False
                break
            else:
                flag = True
        if flag:
            ans = [i,j,tempH]
            break
    if flag:
        break

print(*ans,sep = " ")
n = int(input())

if 7 in n:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n = int(input())
num = []
while n>0:
  num.append(n%10)
  n //= 10

ans = 0
for i in num:
  if i == 7:
    ans+=1
    break
  else:
    ans = 0
    
if ans >= 1:
  print("Yes")
elif ans==0:
  print("No")
N , M =map(int,input().split())
A_n =list(map(int,input().split()))

B_n=sorted(A_n)
i =0
count =len(B_n)
while B_n[i] < sum(B_n)/(4*M) and i-1<=len(B_n):
    i +=1
    count -=1
if count >= M:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

B_n=sorted(A_n,reverse=True)

if B_n[M-1] >= sum(B_n)/(4*M) :
    print('Yes')
else:
    print('No')
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
dict_r = {}
for i in range(vertex):
    dict_r[(r,i)] = infty

dict_c = {}
for i in range(edge):
    data = list(map(int, input("").split()))
    if int(data[0]) == r:
        dict_r[(data[0],data[1])] = int(data[2])
    else:
        dict_c[(data[0],data[1])] = int(data[2])
del data

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global dict_r, dict_c, infty
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > dict_r[(root, i)]:
                min_cost = dict_r[(root, i)]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if ((min_node, i) in dict_c.keys()) == True:
                if dict_r[(root, i)] > dict_r[(root, min_node)] + dict_c[(min_node, i)]:
                    dict_r[(root, i)] = dict_r[(root, min_node)] + dict_c[(min_node, i)]

Dijkstra(r, vertex)

for i in range(vertex):
    if r == i:
        print(0)
    elif dict_r[(r, i)] == infty:
        print("INF")
    else:
        print(dict_r[(r, i)])



### FIXED CODE ###

# Single Source Shortest Path
import heapq

[vertex, edge, r] = list(map(int, input("").split()))
infty = 999999999
final_c = [infty for i in range(vertex)]
dict_c = [[] for i in range(vertex)]

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    dict_c[e1].append((e2, c))

final_c[r] = 0
root_c = [(final_c[r], r)]

def Dijkstra(root, n):
    global infty, root_c, final_c, dict_c, root_c
    while(root_c):
        (cost, v) = heapq.heappop(root_c)
        if cost > final_c[v]:
            continue
        for i in range(len(dict_c[v])):
            (e2, c) = dict_c[v][i]
            if final_c[e2] > final_c[v] + c:
                final_c[e2] = final_c[v] + c
                heapq.heappush(root_c, (final_c[e2], e2))

Dijkstra(r, vertex)
for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print(final_c[i])
N, M = map(int, input().split(" "))
data = []
for i in range(N):
  A = list(map(int, input().split(" ")))
  A_ = A[1:].sort()
  data.append(A_)
  
counter = 0  
for m in range(M):
  flag = 1
  for d in data:
    if m in d:
      flag *= 1
    else:
      flag *= 0
  if flag == 1:
    counter += 1

print(counter)
      
    

### FIXED CODE ###

N, M = map(int, input().split(" "))
data = []
for i in range(N):
  A = list(map(int, input().split(" ")))
  A_ = sorted(A[1:])
  data.append(A_)
  
counter = 0  
for m in range(M):
  flag = 1
  for d in data:
    if m+1 in d:
      flag *= 1
    else:
      flag *= 0
  if flag == 1:
    counter += 1

print(counter)
M = 10**6; dp = [-1]*M; dp[0],dp[1] = 0,0;
def collatz(n):
    if dp[n]!=-1: return dp[n]
    dp[n] = 1+collatz(n/2 if n%2==0 else 3*n+1)
    return dp[n]
while 1:
    n = input()
    if n==0: break
    print collatz(n)

### FIXED CODE ###

def collatz(n):
    if n==1: return 0
    return 1+collatz(n/2 if n%2==0 else 3*n+1)
while 1:
    n = input()
    if n==0: break
    print collatz(n)
from operator import itemgetter
from queue import deque

N = int(input())

xin, yin = [], []
for _ in range(N):
    x, y = map(int, input().split())
    xin.append(x)
    yin.append(y)

x = sorted(list(enumerate(xin)), key=itemgetter(1))
y = sorted(list(enumerate(yin)), key=itemgetter(1))

xds = []
yds = []

for i in range(N-1):
    xds.append((x[i+1][1] - x[i][1],(x[i][0], x[i+1][0])))
    yds.append((y[i+1][1] - y[i][1],(y[i][0], y[i+1][0])))
    
xdq = deque(sorted(xds))
ydq = deque(sorted(yds))

par = list(range(N))

def find(x):
    if x == par[x]:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def union(x, y):
    px, py = find(x), find(y)
    par[px] = py

ans = 0    
while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i, j) = xdq.popleft()
    else:
        d, (i, j) = ydq.popleft()
        
    if find(i) != find(j):
        ans += d
        union(i, j)
print(ans)

### FIXED CODE ###

from operator import itemgetter
from queue import deque

N = int(input())

xin = []
yin = []

for _ in range(N):
    x, y = map(int, input().split())
    xin.append(x)
    yin.append(y)
    
xin = sorted(list(enumerate(xin)), key=itemgetter(1))
yin = sorted(list(enumerate(yin)), key=itemgetter(1))

xd = []
yd = []

for i in range(N-1):
    xd.append((xin[i+1][1] - xin[i][1], (xin[i][0], xin[i+1][0])))
    yd.append((yin[i+1][1] - yin[i][1], (yin[i][0], yin[i+1][0])))
    
xdq = deque(sorted(xd))
ydq = deque(sorted(yd))

par = list(range(N))

def find(x):
    if x == par[x]:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
    
def union(x, y):
    px, py = find(x), find(y)
    if px != py:
        par[py] = px
    
ans = 0

while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i, j) = xdq.popleft()
    else:
        d, (i, j) = ydq.popleft()
        
    if find(i) != find(j):
        ans += d
        union(i, j)
        
print(ans)
n=int(input())
a=list(map(int,input().split()))

a.sort()

table=[True]*1000001
count=0
if n==1:
  count=1
else:
  for i in range(0,n):
    pp=a[i]
    if table[pp]==True:
      if i==0:
        if a[i]!=a[i+1]:
          count+=1
          for j in range(pp,1000002,pp):
            table[j]=False
      elif i==n-1:
        if a[i]!=a[i-1]:
          count+=1
          for j in range(pp,1000002,pp):
            table[j]=False
      else:
        if a[i]!=a[i+1] and a[i]!=a[i-1]:
          count+=1
          for j in range(pp,1000002,pp):
            table[j]=False
      
print(count)
  

### FIXED CODE ###

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

a.sort()

table=[True]*1000001
count=0
if n==1:
  count=1
else:
  for i in range(0,n):
    pp=a[i]
    if table[pp]==True:
      if i==0:
        if pp!=a[i+1]:
          count+=1
        for j in range(pp,1000001,pp):
          table[j]=False
      elif i==n-1:
        if pp!=a[n-2]:
          count+=1
      else:
        if pp!=a[i+1] and pp!=a[i-1]:
          count+=1
        for j in range(pp,1000001,pp):
          table[j]=False
      
print(count)
n,m=input().split()
n=int(n)
m=int(m)
li=[int(k) for k in input().split()]
dp=[0]*n
dp[0]=0
dp[1]=li[1]-li[0]
for i in range(2,n):
  ans=10**9
  for j in range(1,m+1):
    ans=min(ans,abs(li[i]-li[i-j])+dp[i-j])
  dp[i]=ans
print(dp[n-1])  


### FIXED CODE ###

n=int(input())
li=[int(k) for k in input().split()]
dp=[0]*(n)
dp[0]=0
dp[1]=abs(li[1]-li[0])

for i in range(2,n):
  dp[i]=min(abs(li[i]-li[i-1])+dp[i-1],abs(li[i]-li[i-2])+dp[i-2])
#print(dp)
print(dp[n-1])
def solve(string):
    n, m, *a = map(int, string.split())
    for i in range(1, n):
        a[i] += a[i - 1]
    l = [0] * m
    for i in range(n):
        l[a[i] % m] += 1
    ans = l[0]
    for i in range(m):
        ans += l[i] * (l[i] - 1) // 2
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))


### FIXED CODE ###

from collections import defaultdict


def solve(string):
    n, m, *a = map(int, string.split())
    for i in range(1, n):
        a[i] += a[i - 1]

    d = defaultdict(int)
    for i in range(n):
        d[a[i] % m] += 1
    ans = d[0]
    for v in d.values():
        ans += v * (v - 1) // 2
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]


def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b


if n == 0:
    print(0)
elif n == 1:
    print(1)
if m == 0:
    print(fib(n))

total = 1
i = 0
for x in a:
    if x == i:
        print(0)
        exit()
    total *= fib(x - i - 1)
    i = x + 1
if a[-1] != n:
    total *= fib(n - (a[-1] + 1))

print(total % 1000000007)

### FIXED CODE ###

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b


n, m = map(int, input().split())
if m == 0:
    print(fib(n) % 1000000007)
    exit()
a = [int(input()) for _ in range(m)]

total = 1
i = 0
for x in a:
    if x == i:
        print(0)
        exit()
    total *= fib(x - i - 1)
    i = x + 1
if a[-1] != n:
    total *= fib(n - (a[-1] + 1))

print(total % 1000000007)
import math
def sol(inp=input):
    n,k=map(int,inp().split())
    res=0
    for dice_m1 in range(n):
        dice=dice_m1+1
        head=max(0,math.ceil(math.log2(k/dice)))
        res+=2**-head
    res/=n
    return res
print(sol())

### FIXED CODE ###

import math
def sol(inp=input):
    n,k=map(int,inp().split())
    res=0
    for dice_m1 in range(n):
        dice=dice_m1+1
        head=max(0,math.ceil(math.log(k/dice,2)))
        res+=2**-head
    res/=n
    return res
print(sol())
a=int(input())
b=int(input())
print(int(((a-1)*(a-2)*(a-3)*(b-1)(b-2)(b-3))**(1/2)))

### FIXED CODE ###

a=int(input())
b=int(input())
l=[1,2,3]
l[a-1]=0
l[b-1]=0
print(sum(l))
import sys

list={"A":"T","T":"A","G":"C","C":"G"}
b = sys.stdin.readline()
print(list[b])

### FIXED CODE ###

#import sys
#input = sys.stdin.readline

list={"A":"T","T":"A","G":"C","C":"G"}
b = input()
print(list[b])
k,s=map(int,input().split())
cnt=0
ans=0
for i in range(k+1):
  for j in range(k+1):
    for k in range(k+1):
      ans=i+j+k
      if ans=s:
        cnt+=1
print(cnt)

### FIXED CODE ###

k,s=map(int,input().split())
print(sum(0<=s-x-y<=k for x in range(k+1) for y in range(k+1)))
#コピペです。
while True:
    a,b,c = input().split()
    n = int(a)
    s = int(b)
    e = int (c)
    if not n+s+e:
        break
    s = s//100*60+s%100
    e = e//100*60+e%100
    t = [0]*60*24    
    for i in range(n):
        m = int(input())
        for j in range(m):
            a,b = input().split()
            ss = int(a)
            ee = int(b)
            t[ss//100*60+ss%100] += 1
            t[ee//100*60+ee%100] -= 1
    cnt = 0
    ans = 0
    ma = -1
    for i in range(e):
        cnt += t[i]
        if i < s:
            continue
        if cnt==0:
            ans += 1
        else:
            if ma < ans:
                ma = ans
                ans = 0
    print(ma if ma > ans else ans)

### FIXED CODE ###

while True:
    n,s,e = input().split()
    n = int(n)
    s = int(s)
    e = int(e)
    if not n+s+e:
        break
    s = s//100*60+s%100
    e = e//100*60+e%100
    t = [0]*(60*24+1)
    for i in range(n):
        m = int(input())
        g = input().split()
        j = 0
        for o in g:
            a = int(o)
            if j%2:
                t[a//100*60+a%100] += 1
            else:
                t[a//100*60+a%100] -= 1
            j += 1
    cnt = n
    ans = 0
    ma = -1
    for i in range(e):
        cnt += t[i]
        if i < s:
            continue
        if cnt:
            ans += 1
        else:
            if ma < ans:
                ma = ans
            ans = 0
    print(ma if ma > ans else ans)
n = int (raw_input())
a = map(int, raw_input().split())
a.reverse.()
for i in a:
print i

### FIXED CODE ###

n = int(raw_input())
a = map(int,raw_input().split())
a.reverse()
for i in a:
    print i,
A, B, C, X = [int(input()) for i in range(4)]
count = 0
for a in A:
    for b in B:
        for c in C:
            if 500*a+100*b+50*c == X:
                count += 1

print(count)


### FIXED CODE ###

A, B, C, X = [int(input()) for i in range(4)]
count = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if 500*a+100*b+50*c == X:
                count += 1

print(count)
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import cmp_to_key
def cmp(store1, store2):
    if store1 == store2:
        return 0
    a1, b1 = store1
    a2, b2 = store2
    return -1 if a2 * (b1 + 1) <= a1 * (b2 + 1) else 1

def resolve():
    n, T = map(int, input().split())
    assert n <= 3000
    AB = [tuple(map(int, input().split())) for _ in range(n)]
    AB.sort(key = cmp_to_key(cmp))

    # dp[i][j] : i まで見て j 個到達するまでに掛かる最短時間
    dp = [T + 1] * (n + 1)
    dp[0] = 0
    for a, b in AB:
        for i in range(n - 1, -1, -1):
            t = dp[i]
            dp[i + 1] = min(dp[i + 1], (a + 1) * (t + 1) + b)

    for i in range(n, -1, -1):
        if dp[i] <= T:
            print(i)
            return
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from bisect import bisect_right
from itertools import accumulate
from functools import cmp_to_key

def cmp(store1, store2):
    if store1 == store2:
        return 0
    a1, b1 = store1
    a2, b2 = store2
    return -1 if a2 * (b1 + 1) <= a1 * (b2 + 1) else 1

def resolve():
    n, T = map(int, input().split())
    AB = []
    zero = []
    for _ in range(n):
        a, b = map(int, input().split())
        if a != 0:
            AB.append((a, b))
        else:
            zero.append(b + 1)

    AB.sort(key = cmp_to_key(cmp))
    zero.sort()
    zero = list(accumulate(zero))

    max_store = 30
    dp = [T + 1] * max_store
    dp[0] = 0
    for a, b in AB:
        for i in range(max_store - 2, -1, -1):
            t = dp[i]
            dp[i + 1] = min(dp[i + 1], (a + 1) * (t + 1) + b)

    res = 0
    for i in range(max_store):
        t = dp[i]
        if t > T:
            break
        rest = T - t
        res = max(res, i + bisect_right(zero, rest))

    print(res)
resolve()