Problem:
 Score : 600 points    Problem Statement AtCoDeer the deer has N cards with positive integers written on them. The number on the i -th card (1≤i≤N) is a_i .
Because he loves big numbers, he calls a subset of the cards good when the sum of the numbers written on the cards in the subset, is K or greater.  Then, for each card i , he judges whether it is unnecessary or not, as follows:   If, for any good subset of the cards containing card i , the set that can be obtained by eliminating card i from the subset is also good, card i is unnecessary.  Otherwise, card i is NOT unnecessary.   Find the number of the unnecessary cards. Here, he judges each card independently, and he does not throw away cards that turn out to be unnecessary.      Constraints  All input values are integers.  1≤N≤5000  1≤K≤5000  1≤a_i≤10^9 (1≤i≤N)       Partial Score  300 points will be awarded for passing the test set satisfying N,K≤400 .         Input The input is given from Standard Input in the following format:  N  K  a_1  a_2 ... a_N       Output Print the number of the unnecessary cards.        Sample Input 1 3 6
1 4 3      Sample Output 1 1  There are two good sets: { 2,3 } and { 1,2,3 }.  Card 1 is only contained in { 1,2,3 }, and this set without card 1 , { 2,3 }, is also good. Thus, card 1 is unnecessary.  For card 2 , a good set { 2,3 } without card 2 , { 3 }, is not good. Thus, card 2 is NOT unnecessary.  Neither is card 3 for a similar reason, hence the answer is 1 .       Sample Input 2 5 400
3 1 4 1 5      Sample Output 2 5  In this case, there is no good set. Therefore, all the cards are unnecessary.       Sample Input 3 6 20
10 4 3 10 25 2      Sample Output 3 3

Solution (Python):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7
    dp = [0]*k
    dp[0] = 1
    for i in range(n):
        aa = a[i]
        if aa >= k:
            continue
        for j in range(k-aa-1, -1, -1):
            dp[aa+j] = (dp[aa+j]+dp[j]) % mod
    b = [1]*n
    for i in range(n):
        if a[i] >= k:
            b[i] = 0
            continue
        aa = a[i]
        dp2 = [0]*k
        for j in range(aa):
            dp2[j] = dp[j]
        for j in range(aa, k):
            dp2[j] = (dp[j]-dp2[j-aa]) % mod
        for j in range(k-aa, k):
            if dp2[j] != 0:
                b[i] = 0
                break
    print(sum(b))


main()

Solution (Python):
N, K = map(int, input().split())
alpha = list(map(int, input().split()))

alpha = sorted(alpha)
ans = N
t = 0

for i in range(N-1, -1, -1) :
    if t+alpha[i] < K :
        t += alpha[i]
    else :
        ans = min(ans, i)

print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
def f(x):
  if a[x]>=k:
    return True
  dp=[False]*k
  dp[0]=True
  y=0
  for i in range(n):
    if i==x:
      continue
    for j in range(y,-1,-1):
      if j+a[i]>=k:
        continue
      dp[j+a[i]]|=dp[j]
    y=min(k-1,y+a[i])
  return sum(dp[k-a[x]:k])
if not f(n-1):
  print(n)
  exit()
if f(0):
  print(0)
  exit()
l,r=0,n-1
while r-l>1:
  mid=(r+l)//2
  if f(mid):
    r=mid
  else:
    l=mid
print(r)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

l=N
for i in range(0,N):
    if A[i]>=K:
        l=i
        break
A=A[:l]
N=l

def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        return True
    else:
        check=0
        for i in range(K-A[num],K):
            check+=pow(2,i)

        for i in range(1,N):
            check=check|(check>>test[i-1])

        return check%2==1
        


if N==0:
    print(0)
elif N==1:
    if A[0]>=K:
        print(0)
    else:
        print(1)
else:
    start=0
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

    if condition(start):
        print(start)
    elif condition(end):
        print(end)
    else:
        print(N)

Solution (Python):
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    
    N,K=MI()
    a=LI()
    a.sort(reverse=True)
    
    
    
    temp=0
    ans=N
    for i in range(N):
        if temp+a[i]<K:
            temp+=a[i]
        else:
            ans=min(ans,N-i-1)
            
    print(ans)
    
    


main()

Solution (Python):
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    
    N,K=MI()
    a=LI()
    a.sort()
    for i in range(N):
        if a[i]>=K:
            a=a[:i]
            break
    N=len(a)
                    
                    
    
    
    def ch(x):
        
        
        dp=[0]*K
        dp[0]=1
        for i in range(N):
            if i==x:
                continue
            else:
                for j in range(K-1,a[i]-1,-1):
                    dp[j]|=dp[j-a[i]]
                
                        
        
        for j in range(K-a[x],K):
            if  dp[j]:
                return True
        return False
            
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    
    
   
    
            
    
    
    

main()

Solution (Python):
def main():
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    N,K=MI()
    a=LI()
    a.sort()
    for i in range(N):
        if a[i]>=K:
            a=a[:i]
            break
    N=len(a)
                    
                    
    
    
    def ch(x):
        
        
        dp=[0]*K
        dp[0]=1
        for i in range(N):
            if i==x:
                continue
            else:
                for j in range(K-1,a[i]-1,-1):
                    dp[j]|=dp[j-a[i]]
                
                        
        
        for j in range(K-a[x],K):
            if  dp[j]:
                return True
        return False
            
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    
    
 
    

main()

Solution (Python):
def d_no_need(N, K, A):
    card = sorted(A, reverse=True)
    s = 0
    ans = 0
    for a in card:
        if s + a < K:
            s += a
            ans += 1
        else:
            ans = 0
    return ans

N,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_no_need(N, K, A))

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
t = 0
res = -1
for i in range(N):
  if t + a[i] < K: t += a[i]
  else: res = i
print(N - res - 1)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    
    import numpy as np
    

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

    def check(num):
        dp = np.zeros((N+1, K), dtype=np.bool)
        dp[0,0] = 1
        for i in range(N):
            
            dp[i+1] |= dp[i]
            
            if i != num and a[i] < K:
                dp[i+1,a[i]:] |= dp[i,:K-a[i]]
        return any(dp[N, -a[num]:])

    left = -1
    right = N
    while right - left > 1:
        mid = (left+right)//2
        if check(mid):
            right = mid
        else:
            left = mid
    print(right)

    
    
    
    
    
    
    
    
    
    
    
    

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import itertools

N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(i): 
    dp = np.zeros(K, dtype = np.bool)
    
    
    dp[0] = True
    for j in itertools.chain(a[:i], a[i+1:]): 
        dp[j:] = np.logical_or(dp[j:], dp[:-j]) 
    return any(dp[K-a[i]:]) 

left = -1
right = N
while right - left > 1:
    mid = (right + left)//2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)

Solution (Python):
'''
1枚抜いてDPをN枚についてやれば良い, がこれでは間に合わない
そこで必要不要の境界を二分探索で探す
するとO(N^2K)→O(NKlogN)となって間に合う

もう1つの方法は分からない
'''

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

    N,K = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    a = a[:bisect_left(a, K)]
    n = len(a)


    import numpy as np
    def dp(omit):
        dp = np.zeros((n+1, K), dtype=np.bool)
        dp[0,0] = 1
        for i in range(n):
            
            dp[i+1] |= dp[i]
            if i != omit and a[i] < K:
                dp[i+1,a[i]:] |= dp[i,:K-a[i]]
        
        for j in range(max(0, K-a[omit]), K):
            if dp[n,j]:
                return True
        
        return False


    
    
    
    
    
    
    
    
    
    
    

    left = 0
    right = n-1
    while left<=right:
        mid = (left+right)//2
        if dp(mid):
            right = mid-1
        else:
            left = mid+1
    print(right+1)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort()
    ans = N
    t = 0
    for i in range(N)[::-1]:
        if t+A[i] < K:
            t += A[i]
        else:
            ans = min(ans, i)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    from array import array
    input = sys.stdin.readline

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

    dp_left = [array('b', [0] * K) for _ in range(N + 1)]
    dp_right = [array('b', [0] * K) for _ in range(N + 1)]
    dp_left[0][0] = 1
    dp_right[0][0] = 1
    for i, a in enumerate(A):
        for j in range(K):
            if dp_left[i][j]:
                dp_left[i + 1][j] = 1
                if j + a < K:
                    dp_left[i + 1][j + a] = 1
    for i, a in enumerate(reversed(A)):
        for j in range(K):
            if dp_right[i][j]:
                dp_right[i + 1][j] = 1
                if j + a < K:
                    dp_right[i + 1][j + a] = 1

    ok = N
    ng = -1
    mid = (ok+ng)//2
    while ok - ng > 1:
        a = A[mid]
        if a >= K:
            ok = mid
            mid = (ok+ng)//2
            continue
        flg = 0
        l = 0
        r = K-1
        while True:
            if dp_right[N-mid-1][r]:
                break
            r -= 1
        while True:
            if K-a <= l+r < K:
                flg = 1
                break
            elif l+r >= K:
                r -= 1
                if r < 0:
                    break
                while True:
                    if dp_right[N-mid-1][r]:
                        break
                    r -= 1
            else:
                l += 1
                if l >= K:
                    break
                while True:
                    if dp_left[mid][l]:
                        break
                    l += 1
                    if l >= K:
                        break
        if flg:
            ok = mid
        else:
            ng = mid
        mid = (ok+ng)//2
    print(ng+1)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = (dp[i-1]|(dp[i-1]<<ls[i-1]))&((1<<k)-1)
  for b in range(k-1,-1,-1):
    if dp[l] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
if m==0:
  print(0)
  exit()
lf = 0
r = m-1
while lf<r:
  mid = (lf+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    lf = mid+1
if r==0:
  t=sepa[0]
  if maxsum(a[t+1:],k)+acc[t]>=k:
    print(0)
  else:
    print(sepa[r]+1)
else:
  print(sepa[r]+1)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = np.zeros(k, dtype=np.int64)
dp[0] = 1
for i in range(n):
  a = A[i]
  dp[a:] += dp.copy()[:-a]

ans = 0
for i in range(n):
  a = A[i]
  for j in range(max(0, k-a), k):
    temp = dp[j::-a*2].sum()
    if j >= a:
      temp -= dp[j-a::-a*2].sum()
    if temp:
      break
  else:
    ans += 1
print(ans)

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))
 
a = sorted(a)
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)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def need(m):
        s=1
        for i in range(n):
            if i==m:continue
            s|=s<<aa[i]
            s&=mask
        
        if s>>k-aa[m]:return True
        return False

    n,k=MI()
    mask=(1<<k)-1
    
    aa=LI()
    aa.sort()
    for i in range(n):
        if aa[i]>k:
            aa=aa[:i]
            break
    n=len(aa)
    
    l=-1
    r=n
    while l+1<r:
        m=(l+r)//2
        
        
        if need(m):r=m
        else:l=m
    print(l+1)

main()

Solution (Python):
N, K, *A = map(int, open(0).read().split())

A.sort(reverse=True)

cur = 0
ans = 0
for a in A:
    if cur + a < K:
        cur += a
        ans += 1
    else:
        ans = 0

print(ans)

Solution (Python):


import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    
    dp = np.zeros(K, dtype=np.bool)
    prev = np.zeros(K, dtype=np.bool)
    dp[0] = prev[0] = 1
    for i in range(N):
        
        if i != omit and A[i] < K:
            prev[A[i]:] |= dp[:K-A[i]]
        dp = prev.copy()
    
    for j in range(max(0, K-A[omit]), K):
        if dp[j]:
            return True
    
    return False

A.sort()
print(bisearch_min(-1, N, check))

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))
 
a = sorted(a)
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)

Solution (Python):
import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    d = {}
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta in d.keys():
                flag = d[ta]
            elif ta>=k:flag=True
            else:
                flag = False
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
                d[ta] = flag
            
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))
 
a = sorted(a)
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)

Solution (Python):
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()
for i in range(N):
    if A[i] >= K:
        A = A[:i]
        break

N = len(A)

def f(n): 
    dp = [0]*K
    dp[0] = 1
    for i in range(N):
        if i == n:
            continue
        for j in range(K-1, A[i]-1, -1):
            dp[j] |= dp[j-A[i]]
            
    res = False
    for j in range(K-A[n], K):
        if dp[j]:
            res = True
            break
    return res

l = -1
r = N
while r-l > 1:
    m = (l+r)//2
    if f(m):
        r = m
    else:
        l = m
        
print(r)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=[min(a,k+1) for a in A]
    A.sort()
    mask=(1<<k)-1

    def check(i): 
        if(k-A[i]<0): return True
        dp=1
        for j in range(n):
            if(i==j): continue
            dp|=(dp<<A[j])
            dp&=mask

        dp>>=(k-A[i])
        return dp>0

    print(bisection(0,n-1,check,left=False))
resolve()

Solution (Python):
import sys
from itertools import chain

n, k, *a = map(int, sys.stdin.read().split())
*a, = map(lambda x: min(k, x), a)

a.sort()

mask = (1 << k) - 1
def is_needed(i):
    res = 1
    for j in chain(a[:i], a[i+1:]):
        res |= res << j
        res &= mask
    return res >> (k - a[i]) 

def main():
    
    lo = 0 
    hi = n 
    while lo != hi:
        i = (lo + hi) // 2
        if is_needed(i):
            hi = i
        else:
            lo = i + 1

    return hi
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
from itertools import chain

n, k, *a = map(int, sys.stdin.read().split())
*a, = map(lambda x: min(k, x), a)

a.sort()

mask = (1 << k) - 1
def is_needed(i):
    res = 1
    for j in chain(a[:i], a[i+1:]):
        res |= res << j
        res &= mask
    return res >> (k - a[i]) 
    

def main():
    lo = 0
    hi = n - 1
    while lo <= hi:
        i = (lo + hi) // 2
        if is_needed(i):
            hi = i - 1
        else:
            lo = i + 1
    
    
    return hi + 1
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
from itertools import chain

n, k, *a = map(int, sys.stdin.read().split())
*a, = map(lambda x: min(k, x), a)
a.sort()

mask = (1 << k) - 1
def is_needed(i):
    if a[i] == k:
        return True
    res = 1
    for j in chain(a[:i], a[i+1:]):
        res |= (res << j)
        res &= mask
    return res >> (k - a[i]) 

def main():
    lo = -1
    hi = n
    while lo + 1 < hi:
        i = (lo + hi) // 2
        if is_needed(i):
            hi = i
        else:
            lo = i
    
    return hi
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import itertools

def fff(x):
    dp=[0]*k
    dp[0]=1
    for u in itertools.chain(a[:x],a[x+1:]):
        h=dp[:]
        for i in range(u,k):
            h[i]=h[i]|dp[i-u]
        dp=h
    cnt=0
    for i in range(max(0,k-a[x]),k):
        cnt+=dp[i]
    if cnt==0:
        return True
    else:
        return False

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
low=0
high=n-1
while high-low>1:
    mid=(high+low)//2
    if fff(mid):    
        low=mid
    else:
        high=mid

if fff(high):
    print(high+1)
elif fff(low):
    print(low+1)
else:
    print(0)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

"""
・「必要」とは～～が存在
・x を含まない、[K-x,K) 内の総和が存在
・集合を指定すると、ある値段より上側
・全体としても単調性がある
"""

N,K,*A = map(int,read().split())

A = [x if x <= K else K + 1 for x in A]
A.sort()

mask = (1 << K) - 1

def test(x):
    
    if A[x] > K:
        return True
    dp = 1
    for a in itertools.chain(A[:x], A[x+1:]):
        dp |= (dp << a)
        dp &= mask
    dp >>= (K - A[x])
    return (dp > 0)

left = -1 
right = N 
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

answer = left + 1
print(answer)

Solution (Python):
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
dp1 = np.zeros((N+1, K), dtype=bool)
dp1[0][0] = 1
for i, a in enumerate(A, 1):
    dp1[i, :] = dp1[i-1, :]
    dp1[i, a:] += dp1[i-1, :-a]
dp2 = np.zeros((N+1, K), dtype=bool)
dp2[N][0] = 1
for i, a in zip(range(N-1, -1, -1), A[::-1]):
    dp2[i, :] = dp2[i+1, :]
    dp2[i, a:] += dp2[i+1, :-a]
ans = 0
for a, d1, d2 in zip(A, dp1[:-1], dp2[1:]):
    if a >= K:
        continue
    d2_ = np.zeros(K+a, dtype=np.int32)
    d2_[a:] = d2
    d2_cum = np.cumsum(d2_)
    d2_diff = d2_cum[a:] - d2_cum[:-a]
    d = d2_diff[::-1] * d1
    if (d == 0).all():
        ans += 1
print(ans)

Solution (Python):
import numpy as np

def main():
    def check(m):
        DP = np.full(k+1, False)
        DP[0] = True
        for i in range(n):
            if i == m:
                continue
            DP[a[i]:] = np.logical_or(DP[a[i]:], DP[:k+1-a[i]])
        return any(DP[i] for i in range(k-a[m], k))

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

    a = [i for i in a if i <k]
    a.sort()
    n = len(a)

    left = -1
    right = n

    while right-left > 1:
        mid = (right+left)//2
        if check(mid):
            right = mid
        else:
            left = mid

    print(right)

main()

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))
 
a = sorted(a)
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)

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
ans = N
psum = 0
for i in range(N-1, -1, -1) :
    if psum+a[i] < K :
        psum += a[i]
    else :
        ans = min(ans, i)
print(ans)

'''
notes:
1-->we include elems that are less than k  
2-->if some x is necessary all elems grtr than x are also necessary 
Base for some x to be necessary:: 
     atleast one of the sums in range [sm-x,sm) must be possible 
     excluding x  
now at any instance after traversing x elements 
we make sure that we have max posible sm <k 
now 
if x+sm <k 
    we cannot include this anyway 
otherwise
    we can make a set with {sm,x} now x is important 
BOOYAH (:
'''

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))

a = sorted(a)
ans = N
psum = 0
for i in range(N-1, -1, -1) :
    if psum+a[i] < K :
        psum += a[i]
    else :
        ans = min(ans, i)

print(ans)

Solution (Python):
n, k = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)

a = 0
maisu = 0
end_maisu = 0
ans = 0
for i in range(n):
    maisu += 1
    a += l[i]
    if a >= k:
        a -= l[i]
        ans += 1
        end_maisu = maisu
        maisu -= 1
end_maisu -= 1
if end_maisu < 0:
    end_maisu = 0

print(n - ans - end_maisu)

Solution (Python):


import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    
    dp = np.zeros(K, dtype=np.bool)
    prev = np.zeros(K, dtype=np.bool)
    dp[0] = prev[0] = 1
    for i in range(N):
        
        if i != omit and A[i] < K:
            prev[A[i]:] |= dp[:K-A[i]]
        dp = prev.copy()
    
    for j in range(max(0, K-A[omit]), K):
        if dp[j]:
            return True
    
    return False

A.sort()
print(bisearch_min(-1, N, check))

Solution (Python):


import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        
        dp[i+1] = np.logical_or(dp[i+1], dp[i])
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] = np.logical_or(dp[i+1,A[i]:], dp[i,:K-A[i]])
    
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    
    return False

A.sort()
print(bisearch_min(-1, N, check))

Solution (Python):


import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        
        dp[i+1] |= dp[i]
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] |= dp[i,:K-A[i]]
    
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    
    return False

A.sort()
print(bisearch_min(-1, N, check))

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

A.sort()

A_set = list(set(A))

A_set = [int(i) for i in A_set]
A_set.sort()



le = -1
ri = len(A_set)
mid = (le + ri) // 2

while ri - le > 1:
    need = 0
    

    DP = [0 for i in range(k)]
    DP[0] = 1
    jogai = 0
    for i in range(n):
        
        if jogai == 0 and A[i] == A_set[mid]:
            jogai = 1
        else:
            for p in range(k-1, A[i]-1, -1):
                DP[p] = int(DP[p-A[i]] or DP[p])
            
    
            
        for p in range(max(0, k-A_set[mid]), k):
            if DP[p] == 1:
                need = 1
                break
        if need == 1:
            break
    
    if need == 1:
        ri = mid
    else:
        le = mid
    mid = (le + ri) // 2


ans = 0

if le != -1:
    jougen = A_set[le]
    for i in range(n):
        if A[i] <= jougen:
            ans += 1

print(ans)

Solution (Python):
n,k,*a=map(int,open(0).read().split())
s=r=0
for x in sorted(a)[::-1]:
	if s+x<k:
		s+=x
		r+=1
	else:
		r=0
print(r)

"""
Σ_[i=m,n]>kのときa(m)以降は凡て必要
(∵ a(i)が必要->a(i+1)が必要)
k-=Σ_[i=m+1,n]として操作を続ける
Σ_[i=1,r]<kとなったときa(r)までが不必要
"""

Solution (Python):
n,k,*a=map(int,open(0).read().split())
s=r=0
for x in sorted(a)[::-1]:
	if s+x<k:s+=x;r+=1
	else:r=0
print(r)