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

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

candidate1 = []
candidate = {}
for i in range(N):
    if i > 1:
        delete_key = []
        for c in candidate.keys():
            if A[i] % c == 0:
                candidate[c]['atari'] += 1
            else:
                candidate[c]['hazure'] += 1        
    elif i == 0:
        candidate1 = make_divisors(A[i])
    elif i == 1:
        candidate2 = make_divisors(A[i])
        prev = -1
        for c in sorted(candidate1 + candidate2):
            if c != prev and prev != -1 and candidate[prev]['atari'] < 2:
                candidate[prev]['hazure'] += 1
            if c not in candidate:
                candidate[c] = {
                    'atari': 1,
                    'hazure': 0
                }
            else:
                candidate[c]['atari'] += 1
            prev = c
        if candidate[prev]['atari'] < 2:
            candidate[prev]['hazure'] += 1            
max = 0
for c in candidate:
    if candidate[c]['hazure'] < 2 and max < c:
        max = c
print(max)

### FIXED CODE ###

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

candidate1 = []
candidate = {}
for i in range(N):
    if i > 1:
        delete_key = []
        for c in candidate.keys():
            if A[i] % c == 0:
                candidate[c]['atari'] += 1
            else:
                candidate[c]['hazure'] += 1        
    elif i == 0:
        candidate1 = make_divisors(A[i])
    elif i == 1:
        candidate2 = make_divisors(A[i])
        prev = -1
        for c in sorted(candidate1 + candidate2):
            if c != prev and prev != -1 and candidate[prev]['atari'] < 2:
                candidate[prev]['hazure'] += 1
            if c not in candidate:
                candidate[c] = {
                    'atari': 1,
                    'hazure': 0
                }
            else:
                candidate[c]['atari'] += 1
            prev = c
        if candidate[prev]['atari'] < 2:
            candidate[prev]['hazure'] += 1            
max = 0
for c in candidate:
    if candidate[c]['hazure'] < 2 and max < c:
        max = c
print(max)
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = [[] * W for i in range(H)]
dic = {}
for i in range(H):
    a = list(map(int, input().split()))
    A[i] = a
    for j in range(W):
        dic[a[j]] = (i + 1, j + 1)

rec = {}


def cal(L, R):
    if (L, R) in rec:
        return rec[(L, R)]
    else:
        p = abs(dic[L + D][0] - dic[L][0]) + abs(dic[L + D][1] - dic[L][1])
        rec[(L, R)] = cal(L + D, R) + p
        return rec[(L, R)]


Q = int(input())
for i in range(Q):
    L, R = map(int, input().split())
    num = 0
    while L != R:
        num += abs(dic[L + D][0] - dic[L][0]) + abs(dic[L + D][1] - dic[L][1])
        L += D
    print(num)

### FIXED CODE ###

from collections import defaultdict
H, W, D = map(int, input().split())
A = [[] * W for i in range(H)]
dic = {}
for i in range(H):
    a = list(map(int, input().split()))
    A[i] = a
    for j in range(W):
        dic[a[j]] = (i + 1, j + 1)

d = defaultdict(int)
for i in range(D + 1, H * W + 1):
    d[i] = d[i - D] + abs(dic[i][0] - dic[i - D][0]) + abs(dic[i][1] - dic[i - D][1])


Q = int(input())
for i in range(Q):
    L, R = map(int, input().split())
    print(d[R] - d[L])
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
list_s = list(s)
list_score = [ list(map(int,input().split(" "))) for i in range(q)]
list_c = []
for i in range(n-1):
    if list_s[i] == "A" and list_s[i+1] == "C":
        list_c.append(1)
    else:
        list_c.append(0)

for i in range(q):
    g = list_score[i]
    print(sum(list_c[g[0]-1:g[1]-1]))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
list_s = list(s)
list_score = [ list(map(int,input().split(" "))) for i in range(q)]
list_c = [0]
a = 0
for i in range(n-1):
    if list_s[i] == "A" and list_s[i+1] == "C":
        a += 1
        list_c.append(a)
    else:
        list_c.append(a)

for i in range(q):
    g = list_score[i]
    print(list_c[g[1]-1]-list_c[g[0]-1])
### BUGGY CODE ###

N, W = [int(i) for i in input().split(' ')]
w = []
v = []
for i in range(N):
    new_w, new_v = [int(i) for i in input().split(' ')]
    w.append(new_w)
    v.append(new_v)
    
dp = [[0 for j in range(W+1)] for i in range(N)]
for j in range(W+1):
    if w[0]<=j:
        dp[0][j] = v[0]
    
for i in range(1,N):
    for j in range(W+1):
        if w[i]<=j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[N-1][W])

### FIXED CODE ###

import copy
N, W = [int(i) for i in input().split(' ')]
dic = {}
dic_num = {}
dic4calc  = {}

for i in range(N):
    new_w, new_v = [int(i) for i in input().split(' ')]
    if new_w in dic:
        dic[new_w].append(new_v)
    else:
        dic[new_w] = [new_v]
        
w = sorted(list(dic.keys()))
for wi in w:
    dic[wi].sort(reverse=True)
    dic_num[wi] = len(dic[wi])
    dic4calc[wi] = 0

cond = []
def rec(i, rest, dic4calc):
    if rest<w[i]:
        cond.append(dic4calc)
        return

    if i+1<len(w):
        new_dic4calc = copy.deepcopy(dic4calc)
        rec(i+1, rest, new_dic4calc)
    if not dic_num[w[i]]-dic4calc[w[i]]==0:
        new_dic4calc = copy.deepcopy(dic4calc)
        new_dic4calc[w[i]] += 1
        rec(i, rest-w[i], new_dic4calc)
    if i+1>=len(w):
        cond.append(dic4calc)
        return

rec(0, W, dic4calc)
ans = 0
for c in cond:
    total = 0
    for wi in w:
        total += sum(dic[wi][:c[wi]])
    if ans < total:
        ans = total
        
print(ans)
### BUGGY CODE ###

import sys;sys.setrecursionlimit(10000000)
M=lambda:map(int,input().split())
n,q=M()
s=[set()for _ in range(n)]
for i in range(n-1):
  a,b=M()
  s[a-1].add(b-1)
  s[b-1].add(a-1)
p=[0]*n
for i in range(q):
  a,b=M()
  p[a-1]+=b
x=[0]*n
def bfs(I,U):
  global x,s
  u=U
  u+=p[I]
  x[I]=u
  for i in s[I]:
    s[i].discard(I)
    bfs(i,u)
bfs(0,0)
print(*x)

### FIXED CODE ###

import sys;input=sys.stdin.readline
from collections import deque
M=lambda:map(int,input().split())
n,q=M()
s=[[]for _ in range(n)]
for i in range(n-1):
  a,b=M()
  s[a-1].append(b-1)
  s[b-1].append(a-1)
p=[0]*n
for i in range(q):
  a,b=M()
  p[a-1]+=b
v=[1]+[0]*(n-1)
d=deque([(0,0)])
while d:
  b,c=d.popleft()
  c+=p[b]
  p[b]=c
  for i in s[b]:
    if v[i]:continue
    v[i]=1
    d.append((i,c))
print(*p)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(4100000)

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def findminsum(lst,K,N):
    inf=10**6
    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]


    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]

    
def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    # cards=list(filter(lambda x:x<K,cards))
    # N=len(cards)
    cards.sort()
    c1i=list(range(N))
    def unneccesity(h):
        if cards[h]>=K:
            return False
        else:
            c=cards[h]
            cards[h]=0
            ret=findminsum(cards,K-c,N)>=K
            cards[h]=c
            return ret
    #nn=0
    nn=biser(ci,unneccesity)
    # for i in range(N):
    #     if cards[i]<K:
    #         c=cards[i]
    #         cards[i]=0
    #         if findminsum(cards,K-c,N)>=K:
    #             nn+=1
    #         cards[i]=c
    #     else:
    #         break
    print(nn+1)


def main2():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    cards.sort()
    mask=lambda c: (1<<(K))-(1<<c)
    def isunnec(i):
        c=cards[i]
        if c>=K:
            return False
        cards[i]=0
        ret=0
        for x in cards:
            if x!=0:
                ret=(((ret+1)<<x)|ret )&mask(0)
        cards[i]=c
        # print(i,bin(ret&mask(K-c)))
        if ret&mask(K-c)>0:
            return False
        else:
            return True
    nn=biser(list(range(N)),isunnec)
    print(nn+1)
    # for x in range(N):
    #     isunnec(x)
if __name__=='__main__':
    #main()
    main2()


### FIXED CODE ###

#4 9
#1 3 5 6
#の時に1（正解は0）と出力されるがACになる

N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)
### BUGGY CODE ###

S = input()

length = len(S)

cnt = 0
temp = int(S[ : 4])
for x in range(length):
    first = temp
    for i in range(x + 4, length + 1):
        if temp % 2019 == 0:
            cnt += 1
        #print(temp, cnt)

        if i < length:
            temp = ((temp % 2019) * 10) % 2019
            temp = (temp + int(S[i])) % 2019
        else:
            if x + 4 < length:
                temp = (first - (int(S[x]) * 1000))
                temp = temp * 10 + int(S[x + 4])


print(cnt)



### FIXED CODE ###

S = input()[::-1]

length = len(S)
dp = [0] * (length + 2)

times = 1
for x in range(1, length + 1):
    dp[x] += dp[x - 1]
    dp[x] %= 2019
    dp[x] += int(S[x - 1]) * times
    dp[x] %= 2019
    times *= 10
    times %= 2019


cnt = [0] * 2020
for x in range(length + 1):
    cnt[dp[x]] += 1

ans = 0
for c in cnt:
    ans += (c * (c - 1)//2)

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

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
MOD = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, n + 1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[-1])

### FIXED CODE ###

n, m = map(int, input().split())
a = [0] * (n + 1)
for _ in range(m):
    a[int(input())] = True
MOD = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
if not a[1]:
    dp[1] = 1

for i in range(2, n + 1):
    if not a[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

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

import sys
input = sys.stdin.readline
import numpy as np

MOD = 10 ** 9 + 7
S = input().rstrip()

ten = np.zeros(13, dtype=np.int64)
ten[:10] += 1
add_all = [ten]
for _ in range(5):
  add_all.append(add_all[-1][np.arange(0,52,4)%13])
  
add_single = [[x * (10 ** i) % 13 for x in range(10)] for i in range(6)]

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

for i,s in enumerate(S[::-1]):
  if s == '?':
    dp = np.convolve(dp, add_all[i%6])
    dp[:12] += dp[13:25]
    dp = dp[:13] % MOD
  else:
    dp = np.roll(dp, add_single[i%6][int(s)])
  
print(dp[5])


### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])
### BUGGY CODE ###

N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
count = [0] * (N+1)
count[0] = 1
mod = 10 ** 9 + 7
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 3
else:
    count[1] = 1
    start = 2
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= mod

print(count[N])

### FIXED CODE ###

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
dp = [0] * (N+1)
dp[0] = 1
a = set()
for _ in range(M):
    a.add(int(input()))
if 1 in a:
    if 2 in a:
        print(0)
        exit()
    dp[2] = 1
    start = 3
else:
    dp[1] = 1
    start = 2
for i in range(start, N+1):
    if i in a:
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
print(dp[N])
### BUGGY CODE ###

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

for i in range(n-1):
    for j in range(i+1,n,1):
        sum += a[i]*a[j]

print(sum%(10**9+7))

### FIXED CODE ###

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

from collections import deque
monster = deque()
monster.append(int(input()))
count = 0
while monster:
    n = monster.pop()
    if n != 1:
        n = n // 2
        monster.append(n)
        monster.append(n)
        count += 1
    else:
        count += 1
print(count)


### FIXED CODE ###

H = int(input())
count = 0
while H != 1:
    H //= 2
    count += 1
ans = 0
for i in range(count +1):
    ans += 2 ** i
print(ans)
### BUGGY CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort(reverse=True)
#print(lst)

if lst[n - 1] == 1:
  if n > 1:
    if lst[n - 1] == lst[n - 2]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  count = 0
  for i in range(n):
    if i < n - 1:
      flag = True
      if (lst[i] == lst[i + 1]) or (lst[i] == lst[i - 1] and i > 0):
        flag = False
      else:
        for j in range(n - 1, i, -1):
          if lst[i] % lst[j] == 0:
            flag = False
            break
      if flag:
        count += 1
    if i == n - 1:
      if n > 1:
        if lst[i] != lst[i - 1]:
          count += 1
      else:
        count += 1
  print(count)

### FIXED CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if 1 in lst:
  count = 0
  for i in range(n):
    if lst[i] == 1:
      count += 1
    if count == 2:
      break
  if count == 1:
    print(1)
  else:
    print(0)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      for j in range(lst[i] * 2, lst[n - 1] + 1, lst[i]):
        tf_lst[j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)
### BUGGY CODE ###

N = int(input())
arr = [list(map(int,input().split())) for i in range(N)]
arr = sorted(arr)
F = [True]*N
P = [0]*N
for i in range(N):
  P[i] = [arr[i][0]-arr[i][1], arr[i][0]+arr[i][1]]
for i in range(N):
  for j in range(i+1,N):
    if F[i]:
      if P[i][1] > P[j][0]:
        F[j] = False
      else:
        break
print(F.count(True))


### FIXED CODE ###

N = int(input())
arr = [list(map(int,input().split())) for i in range(N)]
arr = sorted(arr, key=lambda x: x[0])
F = [True]*N
P = [0]*N
for i in range(N):
  P[i] = [arr[i][0]-arr[i][1], arr[i][0]+arr[i][1]]
P = sorted(P,key=lambda x:x[1])
ind = 0
for i in range(1,N):
  if P[i][0] < P[ind][1]:
    F[i] = False
  else:
    ind = i
print(F.count(True))
### BUGGY CODE ###

n=int(input())
s=str(input())
ans=0
for i in range(0,1000):
  temp=[]
  temp.append(i//100)
  temp.append((i-(i//100)*100)//10)
  temp.append(i%10)
  cnt=0
  k=0
  for j in range(0,n):
    if cnt==0 and temp[0]==int(s[j]):
      cnt=cnt+1
      k=j
      break
  for j in range(k+1,n):      
    if cnt==1 and temp[1]==int(s[j]):
      cnt=cnt+1
      k=j
      break
  for j in range(k+1,n):
    if cnt==2 and temp[2]==int(s[j]):
      ans=ans+1
      break
print(ans)

### FIXED CODE ###

n=int(input())
s=str(input())
ans=0
i=0
while i<1000:
  temp=i//100
  cnt=0
  k=0
  for j in range(0,n):
    if temp==int(s[j]):
      cnt=cnt+1
      k=j
      break
  if cnt==0:
    i=i+100
  else:
    temp=(i-(i//100)*100)//10
    for j in range(k+1,n):      
      if temp==int(s[j]):
        cnt=cnt+1
        k=j
        break
    if cnt==1:
      i=i+10
    else:
      temp=i%10
      i=i+1
      for j in range(k+1,n):
        if temp==int(s[j]):
          ans=ans+1
          break
print(ans)
### BUGGY CODE ###

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

    dp = [[0]*n for _ in range(k+1)]
    for i in range(n):
        dp[0][i] = A[i]

    flag = False
    for i in range(1,k+1):
        pos = [0]*n
        neg = [0]*n

        for j in range(n):
            pwr = dp[i-1][j]
            pos[max(0,j-pwr)]+=1
            neg[min(n-1,j+pwr)]+=1

        ac_pos = 0
        ac_neg = 0
        for j in range(n):
            ac_pos += pos[j]
            ac_neg += neg[j]
            pos[j] = ac_pos
            neg[j] = ac_neg

        if pos[0]==n and neg[n-1]==n:
            flag = True
            break

        dp[i][0] = pos[0]
        for j in range(1,n):
            dp[i][j] = pos[j] - neg[j-1]
    
    if flag:
        for j in range(n-1):
            print(n, end=" ")  
        print(n)

    else:
        for j in range(n-1):
            print(dp[i][j], end=" ")
        print(dp[i][n-1])
main()

### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))
    k = min(50,k)

    dp = [[0]*n for _ in range(k+1)]
    for i in range(n):
        dp[0][i] = A[i]

    flag = False
    for i in range(1,k+1):
        pos = [0]*n
        neg = [0]*n

        for j in range(n):
            pwr = dp[i-1][j]
            pos[max(0,j-pwr)]+=1
            neg[min(n-1,j+pwr)]+=1

        ac_pos = 0
        ac_neg = 0
        for j in range(n):
            ac_pos += pos[j]
            ac_neg += neg[j]
            pos[j] = ac_pos
            neg[j] = ac_neg

        if pos[0]==n and neg[n-2]==0:
            flag = True
            break

        dp[i][0] = pos[0]
        for j in range(1,n):
            dp[i][j] = pos[j] - neg[j-1]

    
    if flag:
        for j in range(n-1):
            print(n, end=" ")  
        print(n)

    else:
        for j in range(n-1):
            print(dp[i][j], end=" ")
        print(dp[i][n-1])
main()
### BUGGY CODE ###

"""
くじ引きを N 回行い、i 回目には種類が文字列 Si

で表される景品を手に入れました。

何種類の景品を手に入れましたか？
"""
n=int(input())
a=[]
for ii in range(n):
	s=input()
	if s in a:
	    pass
	else:
	    a.append(s)
#print(a)
print(len(a))

### FIXED CODE ###

n=int(input())
a=[]
for ii in range(n):
	s=input()
	a.append(s)

#print(a)
#print(len(a))
print(len(list(set(a))))
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
b = 1
for i in a:
  b = b * i
if b > 1000000000000000000:
  print('-1')
else:
  print(b)

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
ans = 1
for i in a:
    ans *= i
    if ans > 10**18:
        print("-1")
        break
else:
    print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)

for _ in range(0, M, 1):
	A[0] >>= 1
	for i in range(1, len(A), 1):
		if A[i - 1] < A[i]:
			A[i], A[i - 1] = A[i - 1], A[i]
		else:
			break

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda o: -int(o), input().split()))
heapq.heapify(A)

for i in range(0, M, 1):
	heapq.heappush(A, -(-heapq.heappop(A) >> 1))

print(-sum(A))
### BUGGY CODE ###

D, G = map(int, input().split())
pc = [[i + 1] + [int(x) for x in input().split()] for i in range(D)]

import math
m = {}
def f(cur, n, pc, left):
    if left <= 0:
        return n
    def g(cur, n, pc, left):
        fp = (cur, left)
        if fp in m: return m[fp]
        m[fp] = f(cur, n, pc, left)
        return m[fp]
    ret = 10**9
    for x in pc:
        i, p, c = x
        if i*100*p > left:
            h = math.ceil(left / (i*100))
            ret = min(ret, n + h)
        else:
            nc = cur.copy()
            nc.add(i)
            npc = pc.copy()
            npc.remove(x)
            h = f(nc, n + p, npc, max(0, left - i*100*p - c))
            ret = min(ret, h)
    return ret

print(f(set(), 0, pc, G))

### FIXED CODE ###

D, G = map(int, input().split())
pc = [[i + 1] + [int(x) for x in input().split()] for i in range(D)]

import math
m = {}
def f(cur, n, left):
    if left <= 0:
        return n
    def g(cur, n, left):
        if cur in m: return m[cur]
        r = m[cur] = f(cur, n, left)
        return r
    ret = 10**9
    for x in pc:
        i, p, c = x
        if (1 << i) & cur: continue
        ip = i*100*p
        if ip > left:
            h = math.ceil(left / (i*100))
            ret = min(ret, n + h)
        else:
            if n + p >= ret: continue
            h = g(cur | (1 << i), n + p, left - ip - c)
            ret = min(ret, h)
    return ret

print(f(0, 0, G))
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
o=[]
[o.append(a.index(i+1)+1) for i in range(N)]
print(*o)

### FIXED CODE ###

def solve(string):
    n, *a = map(int, string.split())
    ans = [0] * n
    for i, _a in enumerate(a, 1):
        ans[_a - 1] = str(i)
    return " ".join(ans)


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

import bisect
L = []
for _ in range(int(input())):
  a, b = map(int, input().split())
  a, b = (a-1)//2, (b-1)//2
  L.append([a,b])
X_1 = [i for i in range(2, 10**5+1)]
X_2 = []
while len(X_1)>0:
  X_2.append(X_1[0])
  X_1 = [x for x in X_1 if x%X_1[0] != 0]
T = [0]*(10**5)
for i in range(10**5-1):
  if bisect.bisect_left(X_2, 2*i+1)!=bisect.bisect_right(X_2, 2*i+1)\
  and bisect.bisect_left(X_2, i+1)!=bisect.bisect_right(X_2, i+1):
    T[i+1]=T[i]+1
  else:
    T[i+1]=T[i]
for l in L:
  print(T[l[1]+1]-T[l[0]])

### FIXED CODE ###

import bisect
L = []
for _ in range(int(input())):
  a, b = map(int, input().split())
  a, b = (a-1)//2, (b-1)//2
  L.append([a,b])
X_1 = [i for i in range(2, 10**5+1)]
X_2 = []
while len(X_1)>0:
  X_2.append(X_1[0])
  X_1 = [x for x in X_1 if x%X_1[0] != 0]
T = [0]*(10**5)
for i in range(10**5-1):
  if bisect.bisect_left(X_2, 2*i+1)!=bisect.bisect_right(X_2, 2*i+1)\
  and bisect.bisect_left(X_2, i+1)!=bisect.bisect_right(X_2, i+1):
    T[i+1]=T[i]+1
  else:
    T[i+1]=T[i]
for l in L:
  print(T[l[1]+1]-T[l[0]])