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

def main():
    import sys
    mod = int(1e9+7)
    input=sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    #S[0]は使わない
    S = [[0]*60 for _ in range(N)]

    tmp = A[-1]
    idx = 0
    while tmp > 0:
        if tmp%2:
            S[-1][idx] += 1
        idx += 1
        tmp //= 2

    for i in range(N-2, 0, -1):
        for j in range(60):
            S[i][j] = S[i+1][j]
        tmp = A[i]
        idx = 0
        while tmp > 0:
            if tmp % 2:
                S[i][idx] += 1
            idx += 1
            tmp //= 2

    ans = 0
    for i in range(N-1):
        tmp = A[i]
        idx = 0
        while tmp > 0:
            if tmp % 2:
                ans += ((N-1-i)-S[i+1][idx])*2**idx

            else:
                ans += S[i+1][idx]*2**idx

            idx += 1
            tmp //= 2

        for x in S[i+1][idx:]:
            ans += x*2**idx%mod
            idx += 1

        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

mod = int(1e9+7)
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(60):
    a = 0
    b = 0
    for j in range(N):
        if A[j] % 2:
            a += 1
        else:
            b += 1
        A[j] //= 2
    ans += a*b*pow(2, i, mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

ans = 0

for i in a:
    if a.count(i) % 2 != 0:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())

myset = set()
for i in range(n):
    a = int(input())
    if a in myset:
        myset.remove(a)
    else:
        myset.add(a)
ans = len(myset)

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

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
B = set(A)
ans = 0
for i in B:
  if A.count(i) > i:
    ans += A.count(i)-i
  elif A.count(i) < i:
    ans += A.count(i)
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
C = Counter(map(int, input().split()))
ans = 0
for i in C:
    if C[i]>i:
        ans += C[i]-i
    elif C[i]<i:
        ans += C[i]
print(ans)
### BUGGY CODE ###

K=input()
D=int(input())
mod=10**9+7

L=len(K)

DP=[[0]*D for i in range(2)]#DP[num][limit]で,一つ前の桁について,「桁和,そこまでKと一致していれば1」の場合の数


for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        DP[1][j%D]+=1
    else:
        DP[0][j%D]+=1

for keta in range(1,L):
    NDP=[[0]*D for i in range(2)]

    for i in range(D):
        for j in range(10):
            NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[0][i])%mod

    for i in range(D):
        for j in range(10):
            if j>int(K[keta]):
                continue
            if j==int(K[keta]):
                NDP[1][(i+j)%D]=(NDP[1][(i+j)%D]+DP[1][i])%mod
            else:
                NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[1][i])%mod

    DP=NDP

print((DP[0][0]+DP[1][0]-1)%mod)

### FIXED CODE ###

K=input()
D=int(input())
mod=10**9+7

L=len(K)

DP=[0]*D#DP[num][limit]で,一つ前の桁について,「桁和,そこまでKと一致していれば1」の場合の数
LIMIT=[]

for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        LIMIT=j%D
    else:
        DP[j%D]+=1

for ketanum in K[1:]:
    NDP=[0]*D

    for i in range(D):
        for j in range(10):
            NDP[(i+j)%D]=(NDP[(i+j)%D]+DP[i])%mod

    for j in range(int(ketanum)):
        NDP[(LIMIT+j)%D]+=1

    LIMIT=(LIMIT+int(ketanum))%D

    DP=NDP

print((DP[0]-1+ (LIMIT==0) )%mod)
### BUGGY CODE ###

if __name__ == '__main__':
    l, r = map(int, input().split())
    min = 2020
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            res = (i * j) % 2019
            if min > res:
                min = res
    print(min)

### FIXED CODE ###

if __name__ == '__main__':
    l, r = map(int, input().split())
    if l + 2019 <= r:
        print(0)
        exit()
    m = 2019
    for i in range(l, r):
        res_i = i % 2019
        for j in range(l + 1, r + 1):
            res_j = j % 2019
            res = (res_i * res_j) % 2019
            if m > res:
                m = res
    print(m)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import itertools

N = int(input())
A = [int(x) for x in input().split()]

# B_x = max {A_y | y\subset x}
# と思ったが、2元ずつ持つ必要がある。
# (値、何番から来たか)
B = []
for n,a in enumerate(A):
    arr = [(a,n)]
    m = n
    while m:
        bit = m & (-m)
        arr += B[n - bit]
        m -= bit
    se = set(arr)
    B.append(sorted(se, reverse=True)[:2])

answer = itertools.accumulate([x+y for (x,i),(y,j) in B[1:]], max)
print('\n'.join(map(str,answer)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from heapq import heappushpop

N = int(input())
A = [int(x) for x in input().split()]

# B_x = max {A_y | y\subset x}
# と思ったが、2元ずつ持つ必要がある。
# (値、何番から来たか)
B = []
for n,a in enumerate(A):
    arr = [(0,0),(a,n)]
    m = n
    while m:
        bit = m & (-m)
        (x,i),(y,j) = B[n-bit]
        if (x,i) != arr[-1]:
            heappushpop(arr,(x,i))
        if (y,j) != arr[-1]:
            heappushpop(arr,(y,j))
        m -= bit
    B.append(arr)

answer = [0]
for (x,i),(y,j) in B[1:]:
    z = answer[-1]
    if z < x + y:
        z = x + y
    answer.append(z)
print('\n'.join(map(str,answer[1:])))
### BUGGY CODE ###

S=list(input())
Q=int(input())
re=True
cnt=0
for i in range(Q):
    q=list(map(str,input().split()))
    if q[0]=='1':
        cnt+=1
        if re==True:
            re=False
        else:
            re=True
    else:
        if re==True:
            if q[1]=='1':
                S.insert(0,q[2])
            else:
                S.append(q[2])
        else:
            if q[1]=='2':
                S.insert(0,q[2])
            else:
                S.append(q[2])
if cnt%2==1:
    S.reverse()
print(*S,sep='')

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
re=True
cnt=0
for i in range(Q):
    q=list(map(str,input().split()))
    if q[0]=='1':
        cnt+=1
        if re==True:
            re=False
        else:
            re=True
    else:
        if re==True:
            if q[1]=='1':
                S.appendleft(q[2])
            else:
                S.append(q[2])
        else:
            if q[1]=='2':
                S.appendleft(q[2])
            else:
                S.append(q[2])
if cnt%2==1:
    S.reverse()
print(*S,sep='')
### BUGGY CODE ###

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


takara_keys = {}
for i in range(N):
    takara = []
    for idx, c in enumerate(c_list):
        if i in c:
            takara.append(idx)
    takara_keys[i] = takara

clear = [1 for _ in range(N)]
def dp(memos, cost):
    if memos == clear:
        return cost
    costs = [10**9]
    for takara, memo in enumerate(memos):
        if memo == 0:
            next_keys = takara_keys[takara]
            for key in next_keys:
                tmp_memos = memos[:]
                for takara_idx in c_list[key]:
                    tmp_memos[takara_idx] = 1
                tmp_cost = cost + a_list[key]
                costs.append(dp(tmp_memos,tmp_cost))
    return min(costs)

length_0_flag = False
for v in takara_keys.values():
    if len(v)==0:
        length_0_flag = True

if length_0_flag:
    print(-1)
else:
    print(dp([0 for _ in range(N)],0))

### FIXED CODE ###

#解説放送見てからの書き直し
import sys
import os
INF = 10**12
ans = INF
N, M = map(int,input().split())
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
C = []
for i in range(M):
    a, b = map(int,input().split())
    A[i] = a  #鍵の金額
    B[i] = b  #開けられる宝箱の種類数
    tmp = list((map(int,input().split())))
    s = 0
    for j in range(b):
        t = tmp.pop(0)-1
        s |= 1 << t
    C.append(s)
    
dp = [INF]*(1<<N) #2^N
dp[0] = 0 #0 = 0b0000の時、スコアは0（まだ1つも鍵を購入してないので）

for s in range(1<<N): #1<<Nは2^N。つまりどの宝箱が開くかの全ての状態
    for j in range(M): # 全ての鍵について見ていく
        t = s | C[j] # 論理和。sには現在どの宝箱が開けられるかの状態、
                     # C[j]にはその新たな鍵が開ける宝箱。
                     # その論理和はこれまでの鍵と新たな鍵でどの宝箱が開けられるか
        cost = dp[s] + A[j] # その鍵を買った時のコスト
        dp[t] = min(dp[t],cost) #新たな宝箱の状態について、コストがより低くなるようなら保存する。
ans = dp[-1] #dp[-1]、つまり0b1111。宝箱が全て開けられる状態。
if ans == INF: #もし0b1111がINFのまま（最初から変わってない）ということはそこにたどり着けなかったということ。
               #つまり、全ての鍵を使っても宝箱を開けられなかった。
    ans = -1
print(ans)
### BUGGY CODE ###

l = input()
m = 10**9+7
ans = 0
c = 1
while len(l) > 1:
  ans = (ans+c*pow(3,len(l)-1,m))%m
  j = 1
  while l[j] == '0':
    j += 1
    if j == len(l):
      j -= 1
      break
  l = l[j:]
  c = (2*c)%m
ans = (ans+(2*int(l)+1)*c)%m
print(ans)

### FIXED CODE ###

l = input()
m = 10**9+7
ans = 0
c = 1
while len(l) > 1:
  ans = (ans+c*pow(3,len(l)-1,m))%m
  j = 1
  while l[j] == '0':
    j += 1
    if j == len(l):
      j -= 1
      break
  l = l[j:]
  c = (2*c)%m
ans = (ans+(2*int(l)+1)*c)%m
print(ans)
### BUGGY CODE ###

N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]

t,a = src[0]
for ti,ai in src[1:]:
    tn = t + (ti - t%ti)%ti
    an = tn // ti * ai
    while an < a:
        tn += ti
        an += ai
    t,a = tn,an
print(t + a)


### FIXED CODE ###

N = input()
rates = [tuple(map(int, raw_input().split())) for i in range(N)]

votes = rates[0]
for i in range(1,N):
    rate_t = rates[i][0]
    rate_a = rates[i][1]
    min_t = votes[0] / rate_t + (1 if votes[0] % rate_t > 0 else 0)
    min_a = votes[1] / rate_a + (1 if votes[1] % rate_a > 0 else 0)
    mag = max(min_t, min_a)
    votes = (rate_t * mag, rate_a * mag)

print sum(votes)
### BUGGY CODE ###

N = int(input())

ans = 0
for i in range(1, N+1, 1):
  if i != N:
    ans += i
    
print(ans)

### FIXED CODE ###

N = int(input())
    
print((N - 1) * N // 2)
### BUGGY CODE ###

a,b=map(int,input().split())
x=[1]
y=[1]
for i in range(2,a//2+1):
  if a%i==0:
    x.append(i)
    while a%i==0:
      a=a//i
  if b%i==0:
    y.append(i)
    while b%i==0:
      b=b//i
print(len(set(x)&set(y)))

### FIXED CODE ###

import fractions
a,b=map(int,input().split())
k=fractions.gcd(a,b)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    
    return arr

 
print(len(factorization(k))+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from math import factorial
def inpl(): return tuple(map(int, input().split()))

def combination(n, r):
    if n < r:
        return 0
    else:
        return factorial(n)//(factorial(r) * factorial(n-r))

N = int(input())
A = inpl()
C = ["" for i in range(N+1)]

for l, a in enumerate(A):
    if type(C[a]) == int:
        i, j = C[a], l
        break
    else:
        C[a] = l

print(N)

X = i + N - j
for k in range(2, N+2):
    total = combination(N+1, k)
    b = combination(X, k-1)
    print((total-b)%(10**9 + 7))

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

n = int(input())
A = inpl()
mod = 10**9 + 7

fct = [1]
inv = [1]

for i in range(1, n+2):
    fct.append((fct[-1]*i)%mod)
    inv.append((pow(fct[i], mod-2, mod)))

def comb(n, k):
    if k < 0 or k > n:
        return 0
    return (fct[n] * inv[n - k] * inv[k]) % mod    

C = ["" for i in range(n+1)]

for l, a in enumerate(A):
    if type(C[a]) == int:
        i, j = C[a], l
        break
    else:
        C[a] = l

print(n)

for k in range(2, n+2):
    total = comb(n+1, k)
    b = comb(n+i-j, k-1)
    res = (total-b)%(mod)
    print(res)
### BUGGY CODE ###

def gcm(a,b):
    g = max(a,b)
    s = min(a,b)
    while g % s != 0:
        g = g % s
    return s

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

    for i in range(n):
        X[i] -= x
        if X[i] < 0:
            X[i] *= -1

    m = X[0]
    for c in X[1:]:
        m = gcm(c,m)

    print(m)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def gcd(g, s):
    while g % s != 0:
        s, g = sorted([g,s])
        g = g % s
    return s

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

    for i in range(n):
        X[i] -= x
        if X[i] < 0:
            X[i] *= -1

    m = X[0]
    for c in X[1:]:
        m = gcd(c,m)

    print(m)

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

a, b = map(int, input().split())
low = min([round(a/2), round(b/2)])
if a == b:
    print(a)
else:
    for i in range(low, 0, -1):
        if a%i==0 and b%i==0:
            print(i)
            break


### FIXED CODE ###

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

def gcd(a, b):
    big = max(a, b)
    small = min(a, b)
    while not big % small == 0:
        big, small = small, big%small
    return small
    
print(gcd(a, b))
### BUGGY CODE ###

a=list(map(int,input().split()))
a.sort()
cnt=0
while(a[1]!=a[2]):
        a[0]+=1
        a[1]+=1
        cnt+=1
if a[1]==a[0]+1:
    a[1]+=1
    a[2]+=1
    cnt+=1
while(a[0]!=a[1]):
    a[0]+=2
    cnt+=1
print(cnt)

### FIXED CODE ###

a=list(map(int,input().split()))
a.sort()
cnt=0
if a[1]!=a[2]:
    cnt=a[2]-a[1]
    a[0]+=cnt
    a[1]+=cnt
if 1==(a[1]-a[0])%2:
    a[1]+=1
    a[2]+=1
    cnt+=1
if a[0]!=a[1]:
    n=int((a[1]-a[0])/2)
    cnt+=n
    #a[0]+=(n*2)
print(cnt)
### BUGGY CODE ###

def reverse(arr, index):
    if len(arr) == index:
        return arr[-1]
    return arr[index]


from bisect import bisect_left, bisect_right
a, b, q = map(int, input().split())
shrine = [int(input()) for _ in range(a)]
temple = [int(input()) for _ in range(b)]

inf = 10**18
for _ in range(q):
    ans = inf
    x = int(input())
    s0 = shrine[bisect_right(shrine, x)-1]
    t0 = temple[bisect_right(temple, x)-1]
    s1 = reverse(shrine, bisect_left(shrine, x))
    t1 = reverse(temple, bisect_left(temple, x))

    for start in [s0, s1]:
        ta = reverse(temple, bisect_left(temple, start))
        tb = temple[bisect_right(temple, start)-1]
        ans = min(
            ans,
            abs(x - start) + abs(ta - start),
            abs(x - start) + abs(tb - start),
        )

    for start in [t0, t1]:
        sa = reverse(shrine, bisect_left(shrine, start))
        sb = shrine[bisect_right(shrine, start)-1]
        ans = min(
            ans,
            abs(x - start) + abs(sa - start),
            abs(x - start) + abs(sb - start),
        )
    print(ans)




### FIXED CODE ###

from bisect import bisect_left, bisect_right
a, b, q = map(int, input().split())
inf = 10**18
shrine = [-inf] + [int(input()) for _ in range(a)] + [inf]
temple = [-inf] + [int(input()) for _ in range(b)] + [inf]

for _ in range(q):
    ans = inf
    x = int(input())
    index_s = bisect_left(shrine, x)
    index_t = bisect_right(temple, x)
    for i in range(index_s-1, index_s+1):
        s = shrine[i]
        i_t = index_t
        t0, t1 = temple[i_t-1], temple[i_t]
        ans = min(
            ans,
            abs(x - s) + abs(s - t0),
            abs(x - s) + abs(s - t1),
        )

    for i in range(index_t-1, index_t+1):
        t = temple[i]
        i_s = index_s
        s0 = shrine[i_s - 1]
        s1 = shrine[i_s]
        ans = min(
            ans,
            abs(x - t) + abs(t - s0),
            abs(x - t) + abs(t - s1),
        )

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

import sys
sys.setrecursionlimit(10**7)
INF=10**18
def rec(z,w,now,t):
    global N
    if dic.get((z,w,now,t),None)!=None:
        return dic[(z,w,now,t)]
    if now==N-1:
        return abs(z-w)
    if t==0:
        res=-INF
        for i in range(now+1,N):
            res=max(res,rec(a[i],w,i,1))
    elif t==1:
        res=INF
        for i in range(now+1,N):
            res=min(res,rec(z,a[i],i,0))
    dic[(z,w,now,t)]=res
    return res

N,Z,W=map(int,input().split())
a=list(map(int,input().split()))
dic={}

print(rec(Z,W,-1,0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**18

def main():
    N,Z,W=map(int,input().split())
    a=list(map(int,input().split()))
    dic={}
    def rec(z,w,now,t):
        if dic.get((now,t),None)!=None:
            return dic[(now,t)]
        if now>=N-1:
            return abs(z-w)
        if not t:
            res=-INF
            for i in range(now+1,N):
                r=rec(a[i],w,i,1)
                res=max(res,r)
        else:
            res=INF
            for i in range(now+1,N):
                r=rec(z,a[i],i,0)
                res=min(res,r)
        dic[(now,t)]=res
        return res

    return rec(Z,W,-1,0)
    
print(main())
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())
c = 0
for i in range(1,n+1):
    # tmp = (math.floor(a*i/b)-a*math.floor(i/b))
    if c < (math.floor(a*i/b)-a*math.floor(i/b)):
        c = (math.floor(a*i/b)-a*math.floor(i/b))
    elif c > 0 and c > (math.floor(a*i/b)-a*math.floor(i/b)):
        print(c)
        exit()
print(c)

### FIXED CODE ###

import math
a,b,n = map(int,input().split())
x = min(b - 1, n)
ans = math.floor((a * x) / b) - a * (math.floor(x / b))
print(ans)
### BUGGY CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
old_idx = 0
for i in range(len(data)):
  p = data[i]
  for j in range(old_idx+1, p):
    prime_bool[j] = False
  old_idx = p
  if prime_bool[p]:
    #print(p)
    k = 2
    while k*p <= max(a):
      prime_bool[k*p] = False
      k += 1

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] > 1:
      count += 1
print(prime_bool.count(True) - count)
#print(prime_bool)


### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = sorted(list(set(a)))
max_ = max(a)+1
prime_bool = [True]*max_
prime_bool[0] = False

for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    #print(p)
    k = 2
    while k*p < max_:
      prime_bool[k*p] = False
      k += 1

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] == 1:
      count += 1
print(count)
#print(prime_bool)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


#A
"""
a,b = LS()
if a == b:
    print("H")
else:
    print("D")
"""

#B
"""
w,a,b = LI()
print(max(max(a,b)-min(a,b)-w,0))
"""

#C
"""

x = I()
a = 0
i = 1
while a < x:
    a += i
    i += 1
print(i-1)
"""

#D
n,k = LI()
a = LI()
a.sort()
a = a[:bisect.bisect_left(a,k)]
n = len(a)
a = a[::-1]
l = -1
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = [0]*k
    dp[0] = 1
    for i in range(n):
        if i == m:continue
        ai = a[i]
        for j in range(k-ai)[::-1]:
            if dp[j]:
                if k_ <= j+ai:
                    l = m
                    break
                dp[j+ai] = 1
        else:
            continue
        break
    else:
        r = m
print(n-r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


#A
"""
a,b = LS()
if a == b:
    print("H")
else:
    print("D")
"""

#B
"""
w,a,b = LI()
print(max(max(a,b)-min(a,b)-w,0))
"""

#C
"""

x = I()
a = 0
i = 1
while a < x:
    a += i
    i += 1
print(i-1)
"""

#D
n,k = LI()
a = LI()
a.sort()
a = a[:bisect.bisect_left(a,k)]
n = len(a)
a = a[::-1]
l = -1
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = [0]*k
    dp[0] = 1
    ma = 0
    for i in range(n):
        if i == m:continue
        ai = a[i]
        for j in range(min(ma+1,k-ai))[::-1]:
            j_ = j+ai
            if dp[j]:
                if k_ <= j_:
                    l = m
                    break
                dp[j_] = 1
                if j_ > ma:
                    ma = j_
        else:
            continue
        break
    else:
        r = m
print(n-r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T
### BUGGY CODE ###

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

# n(n-1)/2 - (n-1)(n-2)/2 = n-1
dic = {}
su = 0
m = 0
for a in An:
  dic[a] = 0
for a in An:
  dic[a] += 1 
for a,n in enumerate(An):
  su = 0
  for d,i in enumerate(dic):
    m = dic[i]
    su += m * (m-1) / 2
    if i == n:
      su += -m+1
  print(int(su))


### FIXED CODE ###

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

# n(n-1)/2 - (n-1)(n-2)/2 = n-1
dic = {}
su = 0
m = 0
for a in An:
  dic[a] = 0
for a in An:
  dic[a] += 1 
for d,i in enumerate(dic):
  su += dic[i] * (dic[i]-1) / 2
for a in An:
  print(int(su - dic[a] + 1))
### BUGGY CODE ###

S = input()
N = len(S)
ans = 0


for i in range(N):
  if S[i] == "W":
    for j in range(i):
      if S[j] =="B":
        ans += 1
print(ans)

### FIXED CODE ###

S = input()
b = 0
ans = 0
 
for s in S:
    if s == 'B':
        b += 1
    else:
        ans += b
 
print(ans)
### BUGGY CODE ###

K = int(input())
A, B = map(int, input().split())
a = 0
K_sum = K
while K <= B:
    if A<=K and K<=B:
        a = 1
        break
    K_sum += K

if a==1:
    print("OK")
else:
    print("NG")

### FIXED CODE ###

K = int(input())
A, B = map(int, input().split())
mod = A % K
dif = B - A
if mod + dif >= K or mod==0:
    print("OK")
else:
    print("NG")
### BUGGY CODE ###

N = int(input())
S = input()

#S = "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"

Slist = list(S)

count = 0
for i in range(len(Slist)):
    for j in range(i+1, len(Slist)):
        for k in range(j+1, len(Slist)):
            if(Slist[i] == Slist[j]):
                break
            notEqualColor = (Slist[i] == Slist[j] or Slist[j] == Slist[k] or Slist[k] == Slist[i])
            notEqualDistance = (j - i == k - j)

            if((notEqualColor or notEqualDistance) == False):
                count += 1

print(count)


### FIXED CODE ###

import collections

N = int(input())
S = input()

CountRGB = collections.Counter(S)

ans = CountRGB["R"] * CountRGB["G"] * CountRGB["B"]

tmp = 0
for i in range(N-2):
    for j in range(i+1, N-1):

        if(2 * j - i > N - 1):
            break

        checker = []
        checker.append(S[i])
        checker.append(S[j])
        checker.append(S[2 * j - i])

        c = collections.Counter(checker)

        if(c["R"] == 1 and c["G"] == 1 and c["B"] == 1):
            tmp +=1

print(ans - tmp)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
A = list(map(int, input().split()))

dp = [0] * (k+1)

for i in range(1, k+1):
    for a in A:
        if i - a < 0:
            break
        if dp[i-a] == 0:
            dp[i] = 1

if dp[k] == 1:
    print("First")
else:
    print("Second")

### FIXED CODE ###

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

dp = [0] * (k+1)

for i in range(1, k+1):
    for a in A:
        if i - a < 0:
            break
        if dp[i-a] == 0:
            dp[i] = 1

if dp[k] == 1:
    print("First")
else:
    print("Second")