AtCoder Beginner Contest 056 - No Need

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-----
3 6
1 4 3

-----Sample Output-----
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.

Source: atcoder | Difficulty: MEDIUM_HARD


Solutions:
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)
main()


import numpy as np
(N, K) = list(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(list(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)


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))


def d_NoNeed(N, K, A):
	a = sorted(A)
	s = t = 0
	for i in range(N - 1, -1, -1):
		if s + a[i] < K:
			s += a[i]
			t += 1
		else:
			t = 0
	return t
(N, K) = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_NoNeed(N, K, A))


def main():
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	ok = N
	ng = -1
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		n = mid
		dp = [0] * (K + 1)
		dp[0] = 1
		for i in range(N):
			a = A[i]
			if i == n or a >= K:
				continue
			for j in range(K, -1, -1):
				dp[min(K, j + a)] |= dp[j]
		rst = any((dp[k] for k in range(max(0, K - A[n]), K)))
		if rst:
			ok = mid
		else:
			ng = mid
	print(ok)
main()


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

def __starting_point():
	ans = main()
	print(ans)
__starting_point()


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
a = sorted(a)
sum_a = 0
ans = 0
for i in range(n - 1, -1, -1):
	if sum_a + a[i] < k:
		sum_a += a[i]
		ans += 1
	else:
		ans = 0
print(ans)


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


(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)


import numpy as np
import itertools
(N, K) = list(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)


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
(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)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, k) = list(map(int, input().split()))
a = list(map(lambda x: min(int(x), k + 1), input().split()))
a.sort()
mask = (1 << k + 1) - 1

def sub(ii):
	dp = 1
	for i in range(n):
		if i == ii:
			continue
		dp |= dp << a[i] & mask
	val = max((i for i in range(k) if dp >> i & 1))
	return val + a[ii] >= k
if sub(0):
	ans = 0
elif not sub(n - 1):
	ans = n
else:
	l = 0
	r = n - 1
	while l < r - 1:
		m = (l + r) // 2
		if sub(m):
			r = m
		else:
			l = m
	ans = l + 1
print(ans)


(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)


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

def card(N, K, A):
	card = sorted(A, reverse=True)
	s = 0
	ans = 0
	for i in card:
		if s + i < K:
			s += i
			ans += 1
		else:
			ans = 0
	return ans
print(card(n, k, a))


(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)


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
	nn = biser(list(range(N)), isunnec) + 1
	print(nn)
main()


(n, k) = map(int, input().split())
(*l,) = list(map(int, input().split()))
l.sort(reverse=True)
m = 0
ans = 0
for i in l:
	if m + i < k:
		m += i
		ans += 1
	else:
		ans = 0
print(ans)


import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter
import numpy as np
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
(N, K) = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))

def bisect_left_callable(fn, x, lo, hi):
	while lo < hi:
		mid = (lo + hi) // 2
		if fn(mid) < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def is_necessary(ai):
	dp = np.zeros(K, dtype=bool)
	dp[0] = 1
	for (i, a) in enumerate(A):
		if i == ai:
			continue
		dp[a:] = dp[a:] | dp[:-a]
	return any(dp[K - A[ai]:])
A.sort()
unnecessary = bisect_left_callable(is_necessary, 1, lo=0, hi=N)
print(unnecessary)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
import numpy as np

def bisearch(t):
	dp = np.full(k + 1, False)
	dp[0] = True
	for i in range(n):
		if i == t:
			continue
		dp[a[i]:] = np.logical_or(dp[a[i]:], dp[:-a[i]])
	return any(dp[max(0, k - a[t]):k])
(l, r) = (-1, n)
while r - l > 1:
	x = (l + r) // 2
	if bisearch(x):
		r = x
	else:
		l = x
print(r)


import sys

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))
(N, K) = MI()
A = LI()
A.sort()

def f(n):
	B = [0] + [A[i] for i in range(N) if i != n]
	dp = [[0] * K for _ in range(2)]
	dp[0][0] = 1
	for i in range(1, N):
		b = B[i]
		for j in range(K):
			if j >= b:
				dp[i % 2][j] = dp[1 - i % 2][j] | dp[1 - i % 2][j - b]
			else:
				dp[i % 2][j] = dp[1 - i % 2][j]
	if sum((dp[(N - 1) % 2][j] for j in range(max(K - A[n], 0), K))) != 0:
		return True
	else:
		return False
left = -1
right = N
while left + 1 < right:
	mid = (left + right) // 2
	if f(mid):
		right = mid
	else:
		left = mid
print(right)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import itertools
(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)


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)


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()


import sys
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
DP = [0 for k in range(K + 1)]
DP[0] = 1
for a in A:
	for k in range(K - a, -1, -1):
		DP[k + a] += DP[k]

def det(t):
	a = A[t]
	if a >= K:
		return False
	DP_rev = [0 for _ in range(K)]
	ans = True
	for i in range(K):
		DP_rev[i] = DP[i]
		if i - a >= 0:
			DP_rev[i] -= DP_rev[i - a]
		if i >= K - a and DP_rev[i] > 0:
			ans = False
			break
	del DP_rev
	return ans
lt = 0
rt = N - 1
if not det(lt):
	print(0)
	sys.exit()
if det(rt):
	print(rt + 1)
	sys.exit()
while rt - lt > 1:
	ct = (lt + rt) // 2
	if det(ct):
		lt = ct
	else:
		rt = ct
print(rt)


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


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()


import sys
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1

def main():
	(N, K) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=1)
	dp0 = [1] * N
	dp1 = [1] * N
	mask = (1 << K) - 1
	for i in range(N - 1):
		if a[i] < K:
			dp0[i + 1] = (dp0[i] | dp0[i] << a[i]) & mask
		else:
			dp0[i + 1] = dp0[i]
		if a[N - i - 1] < K:
			dp1[N - i - 2] = (dp1[N - i - 1] | dp1[N - i - 1] << a[N - i - 1]) & mask
		else:
			dp1[N - i - 2] = dp1[N - i - 1]
	ans = 0

	def nibutan(ok, ng):
		while abs(ok - ng) > 1:
			mid = (ok + ng) // 2
			if solve(mid):
				ok = mid
			else:
				ng = mid
		return ok

	def solve(i):
		if a[i] < K:
			mask2 = (1 << a[i]) - 1 << K - a[i]
			for j in range(dp0[i].bit_length()):
				if j > mask2.bit_length():
					return True
				if dp0[i] >> j & 1:
					if dp1[i] & mask2 >> j:
						return True
		else:
			return True
		return False
	res = nibutan(-1, N)
	print(N - 1 - res)
main()


import sys

def read_int_list():
	return list(map(int, input().split()))

def read_int():
	return int(input())

def read_str_list():
	return input().split()

def read_str():
	return input()

def solve(n, k, a):
	filter(lambda x: x < k, a)
	n = len(a)
	a.sort()
	s = 0
	lowest = None
	for i in range(n - 1, -1, -1):
		if k - a[i] <= s:
			lowest = i
		else:
			s += a[i]
	if lowest is None:
		return n
	return lowest
(n, k) = read_int_list()
a = read_int_list()
res = solve(n, k, a)
print(res)


import bisect
from collections import deque
(N, K) = map(int, input().split())
a = sorted(map(int, input().split()))
a_k = bisect.bisect_left(a, K, lo=0, hi=N)
A = a[:a_k][::-1]
tmp = 0
N = result = N - (N - a_k)
for (n, i) in enumerate(A):
	if tmp + i >= K:
		result = N - (n + 1)
	else:
		tmp += i
print(result)


(N, K) = map(int, input().split())
A = sorted(filter(lambda x: x < K, list(map(int, input().split()))))
N = len(A)
if N == 0:
	print(0)
	exit()

def judge(x):
	DP = 1
	Z = (1 << K) - 1
	for i in range(N):
		if i != x:
			DP = (DP | DP << A[i]) & Z
	r = 0
	for i in range(K - A[x], K):
		r |= DP & 1 << i
	return r
if judge(0):
	print(0)
	exit()
(L, R, M) = (1, N, 0)
while L != R:
	M = (L + R) // 2
	if judge(M) == 0:
		L = max(L + 1, M)
	else:
		R = M
print(L)


def d_no_need(N, K, A):
	from bisect import bisect_left
	A.sort()
	a_sorted = A[:bisect_left(A, K)]
	ans = len(a_sorted)
	dp = [False] * K
	dp[0] = True
	current_max = 0
	for (idx, a) in reversed(list(enumerate(a_sorted))):
		if current_max + a >= K:
			ans = idx
		updated = True
		for j in range(min(current_max, K - a - 1), -1, -1):
			if dp[j]:
				dp[j + a] = True
				if updated:
					current_max = max(current_max, j + a)
					updated = False
	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))


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)
main()


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 list(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))


import numpy as np

def check(x):
	dp = np.zeros(k, np.bool)
	dp[0] = True
	for e in a[:x] + a[x + 1:]:
		dp[e:] |= dp[:-e]
	return dp[-a[x]:].any()
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
lb = -1
ub = n
while ub - lb > 1:
	m = (lb + ub) // 2
	if check(m):
		ub = m
	else:
		lb = m
print(ub)


def main():
	(N, K) = map(int, input().split())
	A = [0] + list(map(int, input().split()))
	rdp_shift = [N + 1] * K
	rdp_shift[0] = 0
	rdp = [0] * K
	rdp[0] = 1
	for i in range(N):
		rdp2 = [0] * K
		for j in range(K):
			if rdp[j] == 1:
				rdp2[j] = 1
			elif j >= A[-i] and rdp[j - A[-i]] == 1:
				rdp2[j] = 1
				rdp_shift[j] = i
		rdp = rdp2
	ldp = [0] * K
	ldp[0] = 1
	S = [0] * (K + 1)
	ans = 0
	for i in range(1, N + 1):
		for j in range(K):
			S[j + 1] = S[j]
			if rdp_shift[j] <= N - i:
				S[j + 1] += 1
		no_need = True
		for lval in range(K):
			if ldp[lval] == 0:
				continue
			rval = S[K - lval] - S[max(0, K - A[i] - lval)]
			if rval > 0:
				no_need = False
				break
		if no_need:
			ans += 1
		ldp2 = [0] * K
		for j in range(K):
			if ldp[j] == 1 or (j >= A[i] and ldp[j - A[i]] == 1):
				ldp2[j] = 1
		ldp = ldp2
	print(ans)
main()


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()


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)


(N, K) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = 0
tmp = 0
for i in a:
	if tmp + i < K:
		ans += 1
		tmp += i
	else:
		ans = 0
print(ans)


(n, k) = [int(item) for item in input().split()]
a = sorted([int(item) for item in input().split()], reverse=True)
count = 0
asum = 0
for item in a:
	if asum + item < k:
		asum += item
		count += 1
	else:
		count = 0
print(count)


from itertools import accumulate

def main():
	(N, K) = map(int, input().split())
	As = list(map(int, input().split()))
	nonzeros = [1]
	for a in As:
		ndp = nonzeros[-1]
		if a <= K:
			ndp |= nonzeros[-1] % (1 << K - a) << a
		nonzeros.append(ndp)
	dp = [0] * (K + 1)
	dp[0] = 1
	acc = list(accumulate(dp)) + [0]
	ans = 0
	for i in range(N, 0, -1):
		a = As[i - 1]
		ndp = []
		for j in range(K + 1):
			t = dp[j] if j < a else dp[j] + dp[j - a]
			ndp.append(0 if t == 0 else 1)
		dp = ndp
		if a < K:
			nonzero = nonzeros[i - 1]
			for y in range(K + 1):
				if nonzero & 1:
					t = K - y - a - 1
					if acc[K - y - 1] > acc[t if t >= 0 else -1]:
						break
				nonzero >>= 1
			else:
				ans += 1
		acc = list(accumulate(dp)) + [0]
	print(ans)
main()


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()


import numpy as np

def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if sum(a) >= k:
		a.sort()
		(L, R) = (-1, n - 1)
		while L + 1 < R:
			P = (L + R + 1) // 2
			if k <= a[P]:
				R = P
				continue
			dp = np.zeros(k + 1, dtype=np.bool)
			dp[0] = True
			for j in range(n):
				if k <= a[j] or j == P:
					continue
				dp[a[j]:] |= dp[:-a[j]]
			f = False
			for j in range(k - a[P], k):
				f |= dp[j]
			if f:
				R = P
			else:
				L = P
		print(R)
	else:
		print(n)

def __starting_point():
	main()
__starting_point()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = n
(s, cnt) = (0, 0)
for i in a:
	cnt += 1
	if s + i < k:
		s += i
	else:
		ans = n - cnt
print(ans)


(n, k) = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
s = 0
need = 0
for i in range(n):
	if s + a[i] < k:
		s += a[i]
	else:
		need = i + 1
print(n - need)


import random
(N, K) = list(map(int, input().split()))
(*V,) = list(map(int, input().split()))
A = [0] * (N + 1)
B = [0] * (N + 1)
MASK = 2 ** (K + 1) - 1
A[0] = 1
for i in range(N):
	if K <= V[i]:
		A[i + 1] = A[i]
	else:
		A[i + 1] = A[i] | A[i] << V[i] & MASK
B[N] = 1 << K
for i in range(N - 1, -1, -1):
	if K <= V[i]:
		B[i] = B[i + 1]
	else:
		B[i] = B[i + 1] | B[i + 1] >> V[i]
ans = N
for i in range(N):
	if K <= V[i]:
		ans -= 1
		continue
	a = A[i]
	b = B[i + 1]
	VM = 2 ** (V[i] + 1) - 2
	l = 1
	while a and b and l:
		if a & 1 and b & VM:
			ans -= 1
			break
		l = max((a & -a).bit_length() - 1, (b & -b).bit_length() - V[i] - 1)
		a >>= l
		b >>= l
print(ans)


def examA():
	N = DI() / dec(7)
	ans = N
	print(N)
	return

def examB():
	ans = 0
	print(ans)
	return

def examC():
	ans = 0
	print(ans)
	return

def examD():
	(N, K) = LI()
	A = LI()
	A.sort()
	mask = (1 << K) - 1
	noneed = -1
	need = N
	while need - noneed > 1:
		i = (need + noneed) // 2
		if A[i] >= K:
			is_need = True
		else:
			dp = 1
			for j in range(N):
				a = A[j]
				if a > K:
					break
				if i == j:
					continue
				dp |= dp << a & mask
			is_need = dp > mask >> A[i]
		if is_need:
			need = i
		else:
			noneed = i
	ans = noneed + 1
	print(ans)
	return
from decimal import getcontext, Decimal as dec
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def I():
	return int(input())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def DI():
	return dec(input())

def LDI():
	return list(map(dec, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = dec('0.000000000001')
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}
getcontext().prec = 28
sys.setrecursionlimit(10 ** 7)
examD()


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()


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)


import numpy as np
(N, K) = list(map(int, input().split()))
A = tuple(map(int, input().split()))
dp_left = np.zeros((N + 1, K), dtype=bool)
dp_right = np.zeros((N + 1, K), dtype=bool)
dp_left[0, 0] = 1
dp_right[N, 0] = 1
for i in range(N):
	dp_left[i + 1] = dp_left[i]
	dp_right[N - i - 1] = dp_right[N - i]
	if (a := A[i]) < K:
		dp_left[i + 1, a:] |= dp_left[i, :-a]
	if (a := A[N - i - 1]) < K:
		dp_right[N - i - 1, a:] |= dp_right[N - i, :-a]
ans = 0
for (i, a) in enumerate(A):
	left_true = np.nonzero(dp_left[i])[0]
	right_true = np.nonzero(dp_right[i + 1])[0]
	ss = np.searchsorted(right_true, K - left_true) - 1
	if all(right_true[ss] + left_true + a < K):
		ans += 1
print(ans)


def main():
	import numpy as np
	from bisect import bisect_left as bl
	mod = 10 ** 9 + 7
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	dp = np.zeros(k, dtype=np.int32)
	dp[0] = 1
	m = bl(a, k)
	for i in range(m):
		aa = a[i]
		dp[aa:] = (dp[aa:] + dp[:k - aa]) % mod

	def b_search(ok, ng):
		while abs(ok - ng) > 1:
			mid = (ok + ng) // 2
			if value(mid):
				ok = mid
			else:
				ng = mid
		return ok

	def value(i):
		if i == -1:
			return True
		if i == m:
			return False
		aa = a[i]
		dp2 = np.zeros(k, dtype=np.int32)
		dp2[:aa] = dp[:aa]
		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:
				return False
		return True
	print(b_search(-1, m) + 1)
main()


(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)


(N, K) = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
su = 0
ans = 0
for a in A:
	if su + a < K:
		su += a
		ans += 1
	else:
		ans = 0
print(ans)


import sys
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def main():
	(N, K) = map(int, input().split())
	A = [0] + list(map(int, input().split()))
	rdp_shift = [N + 1] * K
	rdp_shift[0] = 0
	rdp = [0] * K
	rdp[0] = 1
	for i in range(1, N):
		rdp2 = [0] * K
		for j in range(K):
			if rdp[j] == 1:
				rdp2[j] = 1
			elif j >= A[-i] and rdp[j - A[-i]] == 1:
				rdp2[j] = 1
				rdp_shift[j] = i
		rdp = rdp2
	ldp = [0] * K
	ldp[0] = 1
	S = [0] * (K + 1)
	ans = 0
	for i in range(1, N + 1):
		for j in range(K):
			S[j + 1] = S[j]
			if rdp_shift[j] <= N - i:
				S[j + 1] += 1
		no_need = True
		for lval in range(K):
			if ldp[lval] == 0:
				continue
			rval = S[K - lval] - S[max(0, K - A[i] - lval)]
			if rval > 0:
				no_need = False
				break
		if no_need:
			ans += 1
		ldp2 = [0] * K
		for j in range(K):
			if ldp[j] == 1 or (j >= A[i] and ldp[j - A[i]] == 1):
				ldp2[j] = 1
		ldp = ldp2
	print(ans)
main()


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()


import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
import queue
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
sys.setrecursionlimit(10000)

def read_int():
	return int(input())

def read_int_n():
	return list(map(int, input().split()))

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input().strip()

def read_str_n():
	return list(map(str, input().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

@mt
def slv(N, K, A):
	A.sort()
	s = 0
	ans = N
	for i in range(N - 1, -1, -1):
		if s + A[i] < K:
			s += A[i]
		else:
			ans = min(ans, i)
	return ans

def main():
	(N, K) = read_int_n()
	A = read_int_n()
	print(slv(N, K, A))
main()


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

def f(N, K, a):
	a.sort()
	if a[0] >= K:
		print(0)
		exit()
	a = [a[i] for i in range(N) if a[i] < K]
	N = len(a)
	ans = N
	dp = [False] * K
	dp[0] = True
	Smax = 0
	for (i, a_) in reversed(list(enumerate(a))):
		if Smax + a_ >= K:
			ans = i
		updated = True
		for j in range(min(Smax, K - a_ - 1), -1, -1):
			if dp[j]:
				dp[j + a_] = True
				if updated:
					Smax = max(Smax, j + a_)
					updated = False
	return ans
print(f(N, K, a))


import sys
import copy
input = sys.stdin.readline
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
SUM = 0
for a in A:
	SUM += a
	if SUM >= K:
		MAX_NO_NEED = a
		break
else:
	print(N)
	sys.exit()
MAX = A.index(MAX_NO_NEED) - 1
A = [a for a in A if a < K]
L = len(A)
MIN = -1
MAX = min(MAX, L - 1)
while MIN != MAX:
	x = (MIN + MAX + 1) // 2
	base = A[x]
	SET = {base}
	flag = 0
	for i in range(L):
		if i == x:
			continue
		a = A[i]
		NSET = copy.copy(SET)
		for j in SET:
			if K <= a + j < K + base:
				flag = 1
				break
			elif a + j < K:
				NSET.add(a + j)
		if flag == 1:
			MAX = x - 1
			break
		SET = NSET
	else:
		MIN = x
		continue
print(MIN + 1)


(N, K) = map(int, input().split())
x = [int(p) for p in input().split()]
x.sort()
x = x[::-1]
pp = 0
ans = 0
for a in x:
	if pp + a < K:
		pp += a
		ans += 1
	else:
		ans = 0
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
temp = 0
ans = 0
for x in a:
	if temp + x < k:
		temp += x
		ans += 1
	else:
		ans = 0
print(ans)


(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)


(N, K) = map(int, input().split())
A = sorted(list(map(int, input().split())))[::-1]
S = 0
ans = 0
for a in A:
	if S + a < K:
		S += a
		ans += 1
	else:
		ans = 0
print(ans)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
B = []
for a in A:
	if a < K:
		B.append(a)
B.sort(reverse=True)
isNeeded = [False] * len(B)
for i in range(len(B) - 1):
	res = B[i]
	stack = [i]
	for j in range(i + 1, len(B)):
		res += B[j]
		stack.append(j)
		if res >= K:
			for s in stack:
				isNeeded[s] = True
			stack.pop()
			res -= B[j]
noNeed = len(B) - sum(isNeeded)
print(noNeed)


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)


import sys
stdin = sys.stdin

def li():
	return [int(x) for x in stdin.readline().split()]

def li_():
	return [int(x) - 1 for x in stdin.readline().split()]

def lf():
	return [float(x) for x in stdin.readline().split()]

def ls():
	return stdin.readline().split()

def ns():
	return stdin.readline().rstrip()

def lc():
	return list(ns())

def ni():
	return int(ns())

def nf():
	return float(ns())
from collections import Counter
(n, k) = li()
a = li()
a_ltk = [ai for ai in a if ai < k]
a_ltk.sort(reverse=True)
need = {ai: False for ai in a_ltk}
for i in range(len(a_ltk)):
	cur = 0
	stack = []
	for j in range(i, len(a_ltk)):
		cur += a_ltk[j]
		stack.append(a_ltk[j])
		if cur >= k:
			for key in set(stack):
				if need[key]:
					continue
				else:
					need[key] = True
			stack.pop()
			cur -= a_ltk[j]
cnt = Counter(a_ltk)
ans = 0
for (k, v) in need.items():
	if not v:
		ans += cnt[k]
print(ans)


import numpy as np
import itertools
(N, K) = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()

def test(i):
	dp = np.zeros(K, dtype=np.bool)
	dp[0] = True
	for a in itertools.chain(A[:i], A[i + 1:]):
		dp[a:] = np.logical_or(dp[a:], dp[:-a])
	return not dp[-A[i]:].any()
left = -1
right = N
while right - left > 1:
	mid = (left + right) // 2
	if test(mid):
		left = mid
	else:
		right = mid
answer = left + 1
print(answer)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
S = 0
ans = 0
for a in A:
	if S + a < K:
		S += a
		ans += 1
	else:
		ans = 0
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
(n, k) = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]
from bisect import *
a.sort()
l = bisect_left(a, k)
ans = n - l
m = sum(a[:l])
dp = [0] * (k + 1)
dp[0] = 1
for ai in reversed(a[:l]):
	for i in range(max(0, k - m), k):
		if dp[i]:
			break
	else:
		break
	ans += 1
	m -= ai
	for i in range(k - ai, -1, -1):
		if dp[i] == 1:
			dp[i + ai] = 1
print(n - ans)


def hersCode(l, r):
	ok = r
	ng = l - 1
	while ok - ng > 1:
		mid = (ok + ng) // 2
		if nasu(a[mid]):
			ok = mid
		else:
			ng = mid
	return ok

def nasu(x):
	if x >= K:
		return True
	D = [0] * K
	L = [0]
	f = 0
	for i in a:
		if i == x and f == 0:
			f = 1
			continue
		for jj in range(len(L) - 1, -1, -1):
			j = L[jj]
			if i + j < K:
				if i + j + x >= K:
					return True
				if D[i + j] == 0:
					D[i + j] = 1
					L.append(i + j)
	return False
(N, K) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
a.append(10 ** 9 + 1)
ans = hersCode(0, N)
print(ans)


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) = list(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)

def __starting_point():
	main()
__starting_point()


import sys
import itertools
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import sys
import itertools
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(N, K) = map(int, input().split())
A = list(sorted(map(int, input().split())))

def check(x):
	if A[x] >= K:
		return True
	dp = [False] * (K + 1)
	dp[0] = True
	for (j, a) in enumerate(A):
		if j == x:
			continue
		for i in range(K, 0, -1):
			if i >= a:
				dp[i] |= dp[i - a]
	for i in range(K - A[x], K):
		if dp[i]:
			return True
	return False
left = -1
right = N
while right - left > 1:
	mid = (left + right) // 2
	if check(mid):
		right = mid
	else:
		left = mid
print(right)


def main():
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	no_need = 0
	sub = 0
	for ai in A:
		if sub + ai < K:
			sub += ai
			no_need += 1
		else:
			no_need = 0
	print(no_need)
main()


import sys
input = sys.stdin.readline
import math
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
MOD = 10 ** 9 + 7
INF = float('inf')
AZ = 'abcdefghijklmnopqrstuvwxyz'

def I():
	return int(input().strip())

def S():
	return input().strip()

def IL():
	return list(map(int, input().split()))

def SL():
	return list(map(str, input().split()))

def ILs(n):
	return list((int(input()) for _ in range(n)))

def SLs(n):
	return list((input().strip() for _ in range(n)))

def ILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def SLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def P(arg):
	print(arg)
	return

def Y():
	print('Yes')
	return

def N():
	print('No')
	return

def E():
	exit()

def PE(arg):
	print(arg)
	exit()

def YE():
	print('Yes')
	exit()

def NE():
	print('No')
	exit()

def DD(arg):
	return defaultdict(arg)

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

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])
	if arr == []:
		arr.append([n, 1])
	return arr

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

def make_primes(N):
	max = int(math.sqrt(N))
	seachList = [i for i in range(2, N + 1)]
	primeNum = []
	while seachList[0] <= max:
		primeNum.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	primeNum.extend(seachList)
	return primeNum

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)

def count_bit(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count

def base_10_to_n(X, n):
	if X // n:
		return base_10_to_n(X // n, n) + [X % n]
	return [X % n]

def base_n_to_10(X, n):
	return sum((int(str(X)[-i - 1]) * n ** i for i in range(len(str(X)))))

def base_10_to_n_without_0(X, n):
	X -= 1
	if X // n:
		return base_10_to_n_without_0(X // n, n) + [X % n]
	return [X % n]

def int_log(n, a):
	count = 0
	while n >= a:
		n //= a
		count += 1
	return count
(N, K) = IL()
A = IL()
A.sort(reverse=True)
ans = 0
now = 0
cnt = 0
for i in range(N):
	a = A[i]
	if now + a >= K:
		ans += cnt + 1
		cnt = 0
	else:
		now += a
		cnt += 1
print(N - ans)


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)

def __starting_point():
	main()
__starting_point()


import sys
(N, K) = map(int, input().split())
a = list(map(int, input().split()))
sum = 0
for i in range(0, N):
	sum += a[i]
if sum < K:
	print(N)
	sys.exit()
if sum == K:
	print(0)
	sys.exit()
a.sort()
a.reverse()
l = N
for i in range(N - 1, -1, -1):
	if a[i] < K:
		l = i
	else:
		break
if l == N:
	print(0)
	sys.exit()
count = N
sum = 0
l_list = []
for j in range(l, N):
	if sum + a[j] < K:
		sum += a[j]
		l_list.append(a[j])
for i in range(0, l):
	if sum + a[i] >= K:
		count -= 1
for i in range(l, N):
	if a[i] in l_list:
		sum = 0
		b = a[:]
		C = b.pop(i)
		for j in range(l - 1, N - 1):
			if sum + b[j] < K:
				sum += b[j]
		if sum + C >= K:
			count -= 1
	else:
		count -= 1
print(count)


(n, k) = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
(a, num, ans) = (sorted(a), 0, n)
for i in range(n - 1, -1, -1):
	if num + a[i] < k:
		num += a[i]
	else:
		ans = i
print(ans)


(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)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ans = N
total = 0
for i in range(N):
	a = A[N - 1 - i]
	if total + a < K:
		total += a
	else:
		ans = min(ans, N - 1 - i)
print(ans)


import sys
input_methods = ['clipboard', 'file', 'key']
using_method = 0
input_method = input_methods[using_method]
tin = lambda : map(int, input().split())
lin = lambda : list(tin())
mod = 1000000007

def main():
	(n, k) = tin()
	al = lin()
	al.sort(reverse=True)
	ss = sum(al)
	arrive = [0] * k
	arrive[0] = 1
	useful_set = set()
	for v in al:
		ss -= v
		u_max = 0
		if v >= k:
			useful_set.add(v)
			continue
		for (i, _) in enumerate(arrive):
			p = k - i - 1
			is_on = arrive[p]
			if is_on == 1 and p + v >= k:
				useful_set.add(v)
				u_max = k
			elif is_on == 1:
				arrive[p + v] = 1
				u_max = max(u_max, p + v)
		if u_max + ss >= k:
			useful_set.add(v)
	ret = 0
	for v in al:
		if v not in useful_set:
			ret += 1
	return ret
isTest = False

def pa(v):
	if isTest:
		print(v)

def input_clipboard():
	import clipboard
	input_text = clipboard.get()
	input_l = input_text.splitlines()
	for l in input_l:
		yield l
if sys.platform == 'ios':
	if input_method == input_methods[0]:
		ic = input_clipboard()
		input = lambda : ic.__next__()
	elif input_method == input_methods[1]:
		sys.stdin = open('inputFile.txt')
	else:
		pass
	isTest = True
else:
	pass
ret = main()
if ret is not None:
	print(ret)


(n, k) = map(int, input().split())
a = [0] + sorted(filter(lambda x: x < k, map(int, input().split())))
n = len(a)

def search(m):
	dp = [1] + [0] * k
	for i in range(n):
		if i == m:
			continue
		for j in range(k, a[i] - 1, -1):
			dp[j] |= dp[j - a[i]]
	for i in range(k - a[m], k):
		if dp[i]:
			return True
	return False
le = 0
ri = n
while ri > le + 1:
	m = (ri + le) // 2
	if search(m):
		ri = m
	else:
		le = m
print(le)


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10 ** 5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right

def LI():
	return list(map(int, stdin.readline().split()))

def LF():
	return list(map(float, stdin.readline().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, stdin.readline().split()))

def II():
	return int(stdin.readline())

def IF():
	return float(stdin.readline())

def LS():
	return list(map(list, stdin.readline().split()))

def S():
	return list(stdin.readline().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

def A():
	(a, b) = LS()
	if a == b:
		print('H')
	else:
		print('D')
	return

def B():
	(w, a, b) = LI()
	(a, b) = (min(a, b), max(a, b))
	if w + a >= b:
		print(0)
		return
	print(b - a - w)
	return

def C():
	n = II()
	x = 0
	for i in range(1, 10 ** 5):
		x += i
		if n <= x:
			print(i)
			return
	return

def D():
	(n, k) = LI()
	a = LI()
	a.sort()
	ok = n
	ng = -1

	def f(x):
		dp = [False] * k
		dp[0] = True
		kx = k - a[x]
		for i in range(n):
			if i == x:
				continue
			ai = a[i]
			for j in range(k - 1, ai - 1, -1):
				if dp[j - ai]:
					dp[j] = True
					if kx <= j:
						return True
		for j in range(max(0, k - a[x]), k):
			if dp[j]:
				return True
		return False
	while ok - ng > 1:
		mid = (ok + ng) // 2
		if f(mid):
			ok = mid
		else:
			ng = mid
	print(ng + 1)
	return
D()


(N, K) = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0
sum = 0
cnt = 0
for i in range(N):
	a = A[i]
	if sum + a >= K:
		ans += cnt + 1
		cnt = 0
	else:
		sum += a
		cnt += 1
print(N - ans)


(n, k) = list(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)


(N, K) = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
cards = 0
tail = N
needs = N
while tail:
	for i in range(tail):
		if A[i] + cards >= K:
			cards += A[i - 1]
			tail = i - 1
			needs = i
			break
	else:
		cards += A[i]
		tail = i
print(needs)


(N, K) = map(int, input().split())
_A = list(map(int, input().split()))
A = []
ans = 0
for a in _A:
	if a >= K:
		ans += 1
	else:
		A.append(a)
M = len(A)
A.sort(reverse=True)
confilm = [0 for _ in range(N)]
sumA = [0 for _ in range(M + 1)]
for i in range(1, M + 1):
	sumA[i] = sumA[i - 1] + A[i - 1]
left = 0
right = 1
while right < M:
	while sumA[right] - sumA[left] >= K:
		left += 1
	for check in range(right, M):
		if sumA[right] - sumA[left] + A[check] >= K:
			confilm[check] = 1
			for i in range(left, right):
				confilm[i] = 1
	right += 1
ans += sum(confilm)
print(N - ans)


import sys
input = sys.stdin.buffer.readline

def solve(mid):
	dp = 1
	mask = (1 << k) - 1
	if k <= a[mid]:
		return False
	for (i, weight) in enumerate(a):
		if i == mid:
			continue
		dp |= dp << min(weight, k + 10)
		dp &= mask
	return dp >> k - a[mid] == 0
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ok = 0
ng = n
if not solve(ok):
	print(0)
	exit()
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	if solve(mid):
		ok = mid
	else:
		ng = mid
print(ok + 1)


(N, K) = list(map(int, input().split(' ')))
A = sorted(list(map(int, input().split(' '))), reverse=True)
result = 0
S = sum(A)
n = len(A)
s = 0
if S < K:
	result = n
elif S == K:
	result = 0
else:
	for i in range(n):
		if s + A[i] >= K:
			result = n - i - 1
		else:
			s += A[i]
print(result)


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a)
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for (bi, b) in enumerate(B):
			if b >= K:
				bi = bi - 1
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
			D.append(0)
			C = D[:]
			if z == 1:
				break
		if z == 0:
			iranaiko.append(a)
print(N - len(need))


from collections import Counter
(N, K) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
a.reverse()
tmp = []
tmp_sum = 0
b = []
for i in a:
	if tmp_sum + i >= K:
		b.append(i)
	else:
		tmp.append(i)
		tmp_sum += i
if len(b) == 0:
	print(N)
else:
	min_num = b[-1]
	c = Counter(a)
	print(N - (a.index(min_num) + c[min_num]))


import sys
sys.setrecursionlimit(300000)

def solve(N: int, K: int, a: 'List[int]'):
	a.sort(reverse=True)
	dp = [False] * K
	dp[0] = True
	ret = 0
	for i in range(N):
		for j in range(K - 1, -1, -1):
			if dp[j]:
				if j + a[i] >= K:
					ret = i + 1
				else:
					dp[j + a[i]] = True
	print(N - ret)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	K = int(next(tokens))
	a = [int(next(tokens)) for _ in range(N)]
	solve(N, K, a)
main()


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()


(N, K) = map(int, input().split())
A = list(map(int, input().split()))
B = []
for a in A:
	if a < K:
		B.append(a)
N = len(B)
B.sort(reverse=True)
check = [True] + [False] * N
dp = [[False] * (K + 1) for i in range(N + 1)]
dp[0][0] = True
for (i, b) in enumerate(B, 1):
	for j in range(K + 1):
		dp[i][j] = dp[i - 1][j]
		if K - b <= j <= K - 1 and dp[i][j]:
			check[i] = True
		if j >= b and dp[i - 1][j - b]:
			dp[i][j] = True
ans = 0
for i in range(N, -1, -1):
	if check[i]:
		break
	ans += 1
print(ans)


(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)