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):
n,k = map(int,input().split())
a = list(map(int,input().split()))

a.sort(reverse=True)
mask = (1<<k)-1
dp = 1
min_n = 10**10
for i in a:
    if(i >= k):
        min_n = i
        continue
    dp |= (dp<<i)
    if(dp > mask):
        min_n = i
        dp &= mask
         
ans = 0
for i in a:
    ans += (i < min_n)

print(ans)

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

a.sort(reverse=True)
mask = (1<<k)-1
dp = 1
min_n = 10**10
for i in a:
    if(i >= k):
        min_n = i
        continue
    dp |= (dp<<i)
    if(dp > mask):
        min_n = i
        dp &= mask
         
ans = 0
for i in a:
    ans += (i < min_n)

print(ans)

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

a.sort(reverse=True)
dp = [False] * (k)
dp[0] = True
min_n = 10**10
for i in a:
    for j in range(k-1,-1,-1):
        if(dp[j]):
            if(j+i >= k):
                min_n = i
            else:
                dp[j+i] = True

ans = 0
for i in a:
    ans += (i < min_n)

print(ans)

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())

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

a.sort(reverse=True)

K = 2*k+1
mask = (1<<K)-1

dpl = [1]
dp = 1
for i in a:
    dp |= (dp<<i)&mask
    dpl.append(dp)


for i in range(n):
    x = dpl[n-1-i]<<a[n-1-i]
    mask = ((1<<a[n-1-i])-1)<<(k)
    
    
    if x&mask:
        print(i)
        break
else: print(n)

Solution (Python):
n, k = map(int,input().split())
a = [k+1 if x > k else x for x in map(int,input().split())]
a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  if a[mid] >= k:
      ng = mid
      continue
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)

Solution (Python):
N,K=map(int,input().split())
b=list(map(int,input().split()))
b.sort()
a=[]
for i in range(N):
    if b[i]<K:
        a.append(b[i])
N=len(a)
ans=0

C=[1]
n=1
for i in range(N):
    n=n|n<<a[i]
    n%=(1<<K)
    C.append(n)

    
if N<=10:
    for i in range(N):
        n=C[i]
        for j in range(i+1,N):
            n=n|n<<a[j]
            n%=(1<<K)
        if n < (1<<K)>>a[i]:
            ans+=1
        else:
            break
    print(ans)
else:
    a+=[10**9]
    H=N
    L=0
    
    while abs(H-L)>4:
        Mid=(H+L)//2
        
        n=1
        for i in range(N):
            if i==Mid:
                continue
            else:
                n=n|n<<a[i]
                n%=(1<<K)
        if n >= (1<<K)>>a[Mid]:    
            H=Mid
        else:
            L=Mid
    
    for j in range(max(0,L-5),N):
        n=1
        for i in range(N):
            if i==j:
                continue
            else:
                n=n|n<<a[i]
                n%=(1<<K)
        if n >= (1<<K)>>a[j]: 
            print(j)
            exit()
    print(N)

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):
from bisect import bisect_left, bisect_right
from itertools import accumulate

def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()
    i = bisect_left(As, K)
    Bs = As[:i]
    M = len(Bs)

    bitsets = [1<<(K-1)]
    bitset = 1<<(K-1)
    for B in Bs:
        bitset |= bitset>>B
        bitsets.append(bitset)
    bitsetRevs = [1<<(K-1)]
    bitset = 1<<(K-1)
    for B in reversed(Bs):
        bitset |= bitset>>B
        bitsetRevs.append(bitset)
    bitsetRevs.reverse()

    def isOK(x):
        B = Bs[x]
        numRevs = [0] * K
        bitset = bitsetRevs[x+1]
        for s in range(K):
            if bitset & (1<<(K-1-s)):
                numRevs[s] = 1
        accNumRevs = list(accumulate([0]+numRevs))
        bitset = bitsets[x]
        for s in range(K):
            if bitset & (1<<(K-1-s)):
                if accNumRevs[K-s] - accNumRevs[max(0, K-s-B)] > 0:
                    return True
        return False

    ng, ok = -1, M
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()

Solution (Python):
from bisect import bisect_left, bisect_right

def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()
    i = bisect_left(As, K)
    Bs = As[:i]
    M = len(Bs)

    def isOK(x):
        bitset = 1<<(K-1)
        for i, B in enumerate(Bs):
            if i == x: continue
            bitset |= bitset>>B
        return bitset & ((1<<Bs[x])-1)

    ng, ok = -1, M
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()

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

dpm = [0]*(N+1)
dpm[0] = 1<<(K-1)
for i, a in enumerate(A):
    dpm[i+1] = dpm[i] | (dpm[i] >> a)

r = 0
dp2 = 1
for i, a in enumerate(A[::-1]):
    for j in range(a):
        if dp2 & dpm[N-i-1]:
            break
        dpm[N-i-1] >>= 1
    else:
        r += 1
    dp2 |= dp2<<a
    dp2 &= (1<<K)-1
print(r)

Solution (Python):

N,K = map(int,input().split())

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

q = 0

a.sort()
a.reverse()
nmax = 0

for i in range(N):

    q += 1
    
    if nmax + a[i] >= K:
        ans -= q
        q = 0

    else:
        nmax = nmax + a[i]

print (ans)

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):
from operator import or_
from functools import reduce
import sys
readline = sys.stdin.readline

def check(a, l, r):
    if (reduce(or_, [r*(1<<k) for k in range(K) if l & (1<<k)])&filt).bit_length() + a > K:
        return True
    else:
        return False

N, K = map(int, readline().split())
A = list(map(int, readline().split()))
A = [a for a in A if a < K]
A.sort()
filt = (1<<K) - 1
M = len(A)
A = [None]+A
dpl = [0]*(M+2)
dpr = [0]*(M+2)
dpl[0] = 1
dpr[M+1] = 1

for i in range(1, M+1):
    dpl[i] = dpl[i-1]*(1<<A[i])&filt |dpl[i-1]

for i in range(M, 0, -1):
    dpr[i] = dpr[i+1]*(1<<A[i])&filt |dpr[i+1]
    
ok = M+1
ng = 0
while abs(ok - ng) > 1:
    med = (ok+ng)//2
    if check(A[med], dpl[med-1], dpr[med+1]):
        ok = med
    else:
        ng = med
print(ng)

Solution (Python):
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
A = [0 if a >= K else a for a in A]
X = [1] * N
Y = [1] * N
m = (1<<K*8) - 1
for i in range(N-1):
    X[i+1] = (X[i] | X[i] << 8 * A[i]) & m if A[i] else X[i]
for i in range(1, N)[::-1]:
    Y[i-1] = (Y[i] | Y[i] << 8 * A[i]) & m if A[i] else Y[i]

ans = N
for i in range(N):
    if A[i] == 0 or ((X[i] * Y[i] & m) >> 8 * (K - A[i])) & ((1 << 8 * A[i]) - 1):
        ans -= 1
print(ans)

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):
N, K = map(int, input().split())
_A = list(map(int, input().split()))
ans = 0

A = []
for a in _A:
    if a >= K:
        ans += 1
    else:
        A.append(a)

A.sort(reverse=True)
M = len(A)
isNess = [False] * M

accA = [0] * (M + 1)
for i in range(1, M + 1):
    accA[i] = accA[i - 1] + A[i - 1]

left = 0
for right in range(1, M):
    while accA[right] - accA[left] >= K:
        left += 1

    for i in range(right, M)[:: -1]:
        if (accA[right] - accA[left]) + A[i] >= K:
            isNess[i] = True
            for j in range(left, i):
                isNess[j] = True
            break

ans += sum(isNess)
print(N - ans)

Solution (Python):
N, K = map(int, input().split())
_A = list(map(int, input().split()))
ans = 0

A = []
for a in _A:
    if a >= K:
        ans += 1
    else:
        A.append(a)

A.sort(reverse=True)
M = len(A)
isNess = [False] * M

accA = [0] * (M + 1)
for i in range(1, M + 1):
    accA[i] = accA[i - 1] + A[i - 1]

left = 0
for right in range(1, M):
    while accA[right] - accA[left] >= K:
        left += 1

    for i in range(right, M):
        if (accA[right] - accA[left]) + A[i] >= K:
            isNess[i] = True
            for j in range(left, right):
                isNess[j] = True

ans += sum(isNess)
print(N - ans)

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


def calc(x):
    if A[x] >= K:
        return True

    dp = [False] * K
    dp[0] = True

    ma = 0
    for i in range(N):
        if i == x:
            continue
        for j in range(ma, -1, -1):
            if j + A[i] >= K:
                continue

            dp[j + A[i]] |= dp[j]

        ma = min(K - 1, ma + A[i])

    return sum(dp[K - A[x]:K])


if not calc(N - 1):
    print(N)
    exit()

if calc(0):
    print(0)
    exit()

l, r = 0, N - 1
while r - l > 1:
    mid = (r + l) // 2
    if calc(mid):
        r = mid
    else:
        l = mid

print(r)

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)


def calc(x):
    if A[x] >= K:
        return True
    dp = [False] * K
    dp[0] = True
    ma = 0
    for i in range(N):
        if i == x:
            continue
        for k in range(ma, -1, -1):
            if k + A[i] >= K:
                continue
            dp[k + A[i]] |= dp[k]
        ma = min(K - 1, ma + A[i])

    return sum(dp[K - A[x]:K])


l, r = 0, N - 1
if not calc(N - 1):
    print(N)
    exit()
if calc(0):
    print(0)
    exit()
while r - l > 1:
    mi = (l + r) // 2
    if calc(mi):
        r = mi
    else:
        l = mi

print(r)

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

As.sort(reverse=True)

minAOK = As[0]+1
sumSubsets = set([0])
for A in As:
    if A >= K:
        minAOK = A
        continue
    for sumSubset in sumSubsets.copy():
        if K - A <= sumSubset:
            minAOK = A
        if sumSubset + A < K:
            sumSubsets.add(sumSubset + A)

ans = len([A for A in As if A < minAOK])
print(ans)

Solution (Python):
import sys

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

fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)

Solution (Python):
from bisect import bisect_left
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()
a=a[:bisect_left(a,K)]
d=[False]*(K)
d[0]=True
curr_max=0
ans=len(a)
for i,a in reversed(list(enumerate(a))):
  if curr_max+a>=K:
    ans=i
  c=curr_max
  for j in range(curr_max+1)[::-1]:
    if j+a<K and d[j]:
      d[j+a]=True
      c=max(c,j+a)
  curr_max=c
print(ans)

Solution (Python):
from collections import defaultdict
import bisect
import sys
def inpl(): return [int(i) for i in input().split()]
def search(a,j):
    if D[j]:
        if D[j] == 1:
            return True
        else:
            return False
    H = defaultdict(lambda: 0)
    H[0] = True
    for i in a:
        for ni in H.copy().keys():
            if ni + i < K-j:
                H[ni+i] = True
                continue
            elif ni + i <= K-1:
                D[j] = 1
                return True
    D[j] = -1
    return False

N, K = inpl()
A = inpl()
A.sort()
A = A[:bisect.bisect_left(A,K)]
M = len(A)
D = defaultdict(lambda: 0)
if sum(A) < K:
    print(M)
    sys.exit()
if sum(A) == K:
    print(0)
    sys.exit()
lo = -1
hi = M
while hi - lo > 1:
    me = (hi+lo)//2
    B = A[:me] + A[me+1:]
    if search(B, A[me]):
        hi = me
    else:
        lo = me
print(hi)

Solution (Python):

from bisect import bisect_left

N, K = map(int, input().split())
A = sorted(map(int, input().split()))
A = A[:bisect_left(A, K)]
dp = [False] * K
dp[0] = True
curr_max = 0
ans = len(A)
for i, a in reversed(list(enumerate(A))):
    
    
    if curr_max + a >= K:
        ans = i

    f = True
    for j in range(min(curr_max, K - a - 1), -1, -1):
        if dp[j]:
            dp[j + a] = True
            if f:
                curr_max = max(curr_max, j + a)
                f = False
print(ans)

Solution (Python):
import sys
N,K=map(int,input().split())
A=sorted([int(i) for i in input().split()])
sa=sum(A)
def f(x):
    y=A[x]
    if y>=K:
        return True
    dp=[False]*(K)
    dp[0]=True
    t=0
    for i in range(N):
        if i==x:
            continue
        s=A[i]
        for k in range(t,-1,-1):
            if k+s>=K:
                continue
            dp[k+s]=dp[k+s]|dp[k]
        t=min(t+s,K-1)
    if sum(dp[K-y:K]):
        return True
    else:
        return False
ma=N-1
mi=0
if not f(N-1):
    print(N)
    sys.exit()
if f(0):
    print(0)
    sys.exit()
while ma-mi>1:
    
    a=(ma+mi)//2
    if f(a):
        ma=a
    else:
        mi=a
print(ma)

Solution (Python):
import sys
N,K=map(int,input().split())
A=sorted([int(i) for i in input().split()])
sa=sum(A)
def f(x):
    y=A[x]
    if y>=K:
        return True
    L=set()
    L.add(0)
    dp=[False]*(K-y)
    dp[0]=True
    t=0
    for i in range(N):
        if i==x:
            continue
        s=A[i]
        for k in range(t,-1,-1):
            if not dp[k]:
                continue
            if k+s>=K:
                continue
            if k+s+y>=K:
                return True
            dp[k+s]=True
        t=min(t+s,K-y-1)
    return False
ma=N-1
mi=0
if not f(N-1):
    print(N)
    sys.exit()
if f(0):
    print(0)
    sys.exit()
while ma-mi>1:
    
    a=(ma+mi)//2
    if f(a):
        ma=a
    else:
        mi=a
print(ma)

Solution (Python):
import bisect


def solve(k, aaa):
    aaa = aaa[:bisect.bisect_left(aaa, k)]

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    ans = len(aaa)
    for i, a in reversed(list(enumerate(aaa))):
        if curr_max + a >= k:
            ans = i
        f = True
        for j in range(min(curr_max, k - a - 1), -1, -1):
            if dp[j]:
                dp[j + a] = True
                if f:
                    curr_max = max(curr_max, j + a)
                    f = False
    return ans


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

print(solve(k, aaa))

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

A = sorted([a for a in A if a < K])
N = len(A)
S = sum(A)


if S < K:
    print(N)
    exit()
elif S - A[0] < N:
    print(0)
    exit()

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if S - A[m] < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    flg= False

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

            if dp[j] and K-A[m] <= j < K:
                r = m
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        l = m

print(r)

Solution (Python):

def inpl(): return list(map(int, input().split()))
 
N, K = inpl()
A = sorted(inpl())
S = []
s = 0
for a in A:
    s += a
    S.append(s)

A = A[::-1]
DP = [True]+[False for _ in range(K-1)]

OK = [False for _ in range(N)]
 
for i, a in enumerate(A):
    DP1 = [False for _ in range(K)]
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP):
        if d:
            DP1[j] = True
            if j + a >= K:
                OK[i] = True
            else:
                DP1[j+a] = True
    DP = DP1

if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Solution (Python):

def inpl(): return list(map(int, input().split()))
 
N, K = inpl()
A = sorted(inpl())
S = []
s = 0
for a in A:
    s += a
    S.append(s)

A = A[::-1]
DP = [True]+[False for _ in range(K-1)]

OK = [False for _ in range(N)]
 
for i, a in enumerate(A):
    DP1 = [False] * K
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP[-S[::-1][i]:], max(0, K-S[::-1][i])):
        if d:
            DP1[j] = True
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP1[j+a] = True
    DP = DP1 
if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,k = LI()
    a = sorted(LI())
    sa = sum(a)
    if sa < k:
        return n
    if sa - a[0] < k:
        return 0

    mi = 0
    ma = n-1

    def f(m):
        am = a[m]
        if am >= k:
            return True

        t = [False] * (k-am)
        t[0] = True
        tl = len(t)
        for i in range(n):
            if i==m:
                continue
            ai = a[i]
            for j in range(tl-1,-1,-1):
                if not t[j]:
                    continue
                if k <= j+ai:
                    continue
                if j+ai >= tl:
                    return True

                t[j+ai] = True

        return False

    while mi < ma:
        m = (mi+ma) // 2
        if f(m):
            ma = m
        else:
            mi = m+1

    return mi


print(main())

Solution (Python):
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
used=[False]*n
idx=n-1
cnt=0
while True:
    if idx-cnt<0:
        break
    tmp=sum(a[idx-cnt:idx+1])
    if tmp<k:
        cnt+=1
        continue
    for i in xrange(idx-cnt,idx+1):
        used[i]=True
    tmp-=a[idx-cnt]
    for i in xrange(idx-cnt-1,-1,-1):
        if tmp+a[i]>=k:
            used[i]=True
        else:
            break
    idx-=1
    cnt=0
ans=0
for i in xrange(n):
    if not used[i]:
        ans+=1
print ans

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

small = 0
while small < n and a[small] < k:
    small += 1
n = small


cnt = 0
able = [False for i in range(k)]
able[0] = True
min_need = n
max_able = 0
i = n-1
while i >= 0:
    if max_able + a[i] >= k:
        min_need = i
        for j in range(min_need):
            if max_able + a[j] >= k:
                min_need = i
                break
    for j in range(min(max_able, k-a[i]-1), -1, -1):
        if able[j]:
            able[j+a[i]] = True
            max_able = max(j+a[i], max_able)
    i -= 1
print(min_need)