Buggy python submission (verdict: Time Limit Exceeded):
import sys





def main():
    def mkns(a,s,m):
        if a==0:
            return s
        else:
            return (((s+1)<<a)|s) & m
    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)
    
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i): 
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
         if a[i]>=K:
             break
         ss[i+1]=mkns(a[i],ss[i],pm)
         if isunnec(i):
             nn+=1
    print(nn)

if __name__=='__main__':
    main()



Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys

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 mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i): 
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=(((ss[i]+1)<<a[j])|ss[i]) & pm
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
        if a[i]>=K:
            break
        ss[i+1]=(((ss[i]+1)<<a[i])|ss[i]) & pm
        if isunnec(i):
            nn+=1
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys

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 mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i): 
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
         if a[i]>=K:
             break
         ss[i+1]=mkns(a[i],ss[i],pm)
         if isunnec(i):
             nn+=1
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Runtime Error):
import sys

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 mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i):
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=(((ss[i]+1)<<a[j])|ss[i]) & pm
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    # for i in range(N):
    #      if a[i]>=K:
    #          break
    #      ss[i+1]=(((ss[i]+1)<<a[i])|ss[i]) & pm
    #      if isunnec(i):
    #          nn+=1
        # for j in range(i+1,N):
        #     if a[j]>=K:
        #         break
        #     ss[i]=mkns(a[j],ss[i],pm)
        # # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        # if ss[i]&mask(K-a[i])==0:
        #     nn+=1
    m=len(list(filter(lambda x:x<K, a)))
    nn=biser(list(range(m)),isunnec)+1
    # print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys

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 mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i): 
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
         if a[i]>=K:
             break
         ss[i+1]=mkns(a[i],ss[i],pm)
         if isunnec(i):
             nn+=1
        # for j in range(i+1,N):
        #     if a[j]>=K:
        #         break
        #     ss[i]=mkns(a[j],ss[i],pm)
        # # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        # if ss[i]&mask(K-a[i])==0:
        #     nn+=1
    # nn=biser(list(range(N)),isunnec)+1
    # print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
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 mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        ss[i+1]=mkns(a[i],ss[i],pm)
    def isunnec(i):
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    nn=biser(list(range(N)),isunnec)+1
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys

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 mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        ss[i+1]=mkns(a[i],ss[i],pm)
    def isunnec(i):
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    nn=biser(list(range(N)),isunnec)+1
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys

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 mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        if a[i]>=K:
            break
        ss[i+1]=mkns(a[i],ss[i],pm)
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-a[i])==0:
            nn+=1
    # def isunnec(i):
    #     for j in range(i+1,N):
    #         if a[j]>=K:
    #             return False
    #         ss[i]=mkns(a[j],ss[i],pm)
    #     # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
    #     if ss[i]&mask(K-c)==0:
    #         return True
    #     return False
    # nn=biser(list(range(N)),isunnec)+1
    # print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        c=a[i]
        if c>=K:
            break
        ss[i+1]=mkns(c,ss[i],pm)
        a[i]=0
        for j in range(N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-c)==0:
            nn+=1
    # print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
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 submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np

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 submission:
#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 python submission (verdict: Time Limit Exceeded):
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]


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()
    ci=list(range(N))
    def inneccesity(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,inneccesity)
    # 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)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Runtime Error):
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]


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()
    ci=list(range(N))
    def func(h):
        c=cards[h]
        cards[h]=0
        ret=findminsum(cards,K-c,N)>=K
        cards[h]=c
        return ret
    #nn=0
    nn=biser(ci,func)
    # 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)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10000)

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        return lst[0]
    if func(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]


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()
    ci=list(range(N))
    def func(h):
        c=cards[h]
        cards[h]=0
        ret=findminsum(cards,K-c,N)>=K
        cards[h]=c
        return ret
    #nn=0
    nn=biser(ci,func)
    # 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)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Runtime Error):
import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        return lst[0]
    if func(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]


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()
    ci=list(range(N))
    def func(h):
        c=cards[h]
        cards[h]=0
        ret=findminsum(cards,K-c,N)>=K
        cards[h]=c
        return ret
    #nn=0
    nn=biser(ci,func)
    # 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)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys

def findminsum(lst,K,N,dp):
    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())
    inf=10**6
    dp=[[inf]*N for s in range(K+1)]
    cards=list(map(int,sys.stdin.readline().strip().split()))
    # cards=list(filter(lambda x:x<K,cards))
    cards.sort()
    N=len(cards)
    nn=0
    for i in range(N):
        if cards[i]<K:
            c=cards[i]
            cards[i]=0
            if findminsum(cards,K-c,N,dp)>=K:
                nn+=1
            cards[i]=c
        else:
            break
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Runtime Error):
import sys

def findminsum(lst,K,N,dp):
    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():
    inf=10**6
    dp=[[inf]*N for s in range(K+1)]
    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))
    cards.sort()
    N=len(cards)
    nn=0
    for i in range(N):
        if cards[i]<K:
            c=cards[i]
            cards[i]=0
            if findminsum(cards,K-c,N,dp)>=K:
                nn+=1
            cards[i]=c
        else:
            break
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys

def findminsum(lst,K,N):
    inf=10**10
    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))
    cards.sort()
    N=len(cards)
    nn=0
    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)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys

def findminsum(lst,K,N):
    inf=10**10
    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.sort()
    nn=0
    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)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Runtime Error):
import sys

def findminsum(lst,K,N):
    inf=10**10
    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]:
                ds[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.sort()
    nn=0
    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)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Runtime Error):
import sys

def findminsum(lst,K,N):
    inf=10**10
    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]
                ds[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.sort()
    nn=0
    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)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys

def findminsum(lst,K,N):
    inf=10**10
    dp=[[(inf if lst[0]<s and j==0 else lst[0]) for j in range(N)] for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if 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()))
    nn=0
    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
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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 python submission (verdict: Time Limit Exceeded):
import sys

def findminsum(lst,K,N):
    inf=10**16
    dp=[[(inf if lst[0]<s and j==0 else lst[0]) for j in range(N)] for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if 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()))
    nn=0
    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
    print(nn)

if __name__=='__main__':
    main()


Fixed submission:
#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)