CodeEff/ECCO huggingface dataset:
# Original solution
#b
#naive (TLE)

n,m = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
colors = [0]*n

for _ in range(m):
    a,b = [int(i) for i in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    
q = int(eval(input()))
info = []
for _ in range(q):
    v,d,c = [int(i) for i in input().split()]
    info.append((v,d,c))
    
info.reverse()
for tupple in info:
    v,d,c = tupple
    
    #bfs
    queue = [v-1]
    while(d>=0):
        next_queue = []
        for p in queue:
            if colors[p]==0:
                colors[p] = c
            nodes = edges[p]
            next_queue += nodes
        d -= 1
        queue = next_queue

for i in range(n):
    print((colors[i]))


# Optimized solution
#b
#by using the condition d<=10, we should memorize V*d whether the pair is already searched.
#if searched, we can stop.

n,m = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
colors = [0]*n

checker = [[0 for _ in range(11)] for _ in range(n)]        

for _ in range(m):
    a,b = [int(i) for i in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    

def dfs(d,v,c):
    if checker[v][d] != 0 or d<0:
        return
    #d>=0 and (v,d) is not checked
    if colors[v]==0: #not colored yet
        colors[v] = c
    checker[v][d] = 1 #checked
    
    dfs(d-1, v, c) #dが低いやつについて全て埋めておく必要がある。もう先着ありで無理ですよ、って宣言。
    
    nodes=edges[v]
    for u in nodes:
        dfs(d-1, u, c)

    
q = int(eval(input()))
info = []
for _ in range(q):
    v,d,c = [int(i) for i in input().split()]
    info.append((v-1,d,c))
    
info.reverse()
for tupple in info:
    v,d,c = tupple
    
    #not bfs but dfs
    dfs(d,v,c)
    
for i in range(n):
    print((colors[i]))
# Original solution
import sys
sys.setrecursionlimit(10**7)

def main():
  n, m = list(map(int, input().split()))
  G = [[] for _ in range(n)]
  for _ in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
  q = int(eval(input()))
  vdc = [list(map(int, input().split())) for _ in range(q)][::-1]
  dp = [[0]*11 for _ in range(n)]
  def dfs(v, d, c):
    if dp[v][d]:
      return dp[v][d]
    if d == 0:
      dp[v][d] = c
      return
    for u in G[v]:
      dfs(u, d-1, c)
    dfs(v, d-1, c)
    dp[v][d] = c
  for v, d, c in vdc:
    dfs(v-1, d, c)
  for i in range(n):
    print((dp[i][0]))
if __name__ == "__main__":
  main()

# Optimized solution
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def main():
  n, m = list(map(int, input().split()))
  G = [[] for _ in range(n)]
  for _ in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
  q = int(eval(input()))
  vdc = [list(map(int, input().split())) for _ in range(q)][::-1]
  dp = [[0]*11 for _ in range(n)]
  def dfs(v, d, c):
    if dp[v][d]:
      return dp[v][d]
    if d == 0:
      dp[v][d] = c
      return
    for u in G[v]:
      dfs(u, d-1, c)
    dfs(v, d-1, c)
    dp[v][d] = c
  for v, d, c in vdc:
    dfs(v-1, d, c)
  for i in range(n):
    print((dp[i][0]))
if __name__ == "__main__":
  main()
# Original solution
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc012 C
"""

from collections import defaultdict

n, m = list(map(int, input().split()))

graph = defaultdict(list)
for i in range(m):
    a, b = list(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)

q = int(eval(input()))
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        dp[v][d] = t
        if d > 0:
            updatedp(v, t, d-1)
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

for i in range(1, n+1):
    print((col[dp[i][0]+1]))


# Optimized solution
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc012 C
"""


n, m = list(map(int, input().split()))

graph = [[] for i in range(n+1)]
for i in range(m):
    a, b = list(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)

q = int(eval(input()))
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        dp[v][d] = t
        if d > 0:
            updatedp(v, t, d-1)
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

for i in range(1, n+1):
    print((col[dp[i][0]+1]))
# Original solution
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc012 C
"""


n, m = list(map(int, input().split()))

graph = [[] for i in range(n+1)]
for i in range(m):
    a, b = list(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)

q = int(eval(input()))
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        dp[v][d] = t
        if d > 0:
            updatedp(v, t, d-1)
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

for i in range(1, n+1):
    print((col[dp[i][0]+1]))


# Optimized solution
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc012 C
"""


n, m = list(map(int, input().split()))

graph = [[] for i in range(n+1)]
for i in range(m):
    a, b = list(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)

q = int(eval(input()))
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        for i in range(d+1):
            if dp[v][i] == -1:
                dp[v][i] = t
        if d > 0:
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

for i in range(1, n+1):
    print((col[dp[i][0]+1]))
# Original solution
n,m = list(map(int,input().split()))
p = [list(map(int,input().split())) for i in range(m)]
q = int(eval(input()))
v = [list(map(int,input().split())) for i in range(q)]
v = v[::-1]
l = [[] for i in range(n+1)]
for pi in p:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
mita = [-1]*(n+1)
tugi = [set() for i in range(n+1)]
iro = [0] *(n+1)
def dfs(x,y,z):
  if iro[x] == 0:
    iro[x] = z
  if mita[x] >=y:
    return
  for i in l[x]:
    if y-1>=0:
      dfs(i,y-1,z)
for ch in v:
  dfs(ch[0],ch[1],ch[2])
for i in range(1,n+1):
  print((iro[i]))

# Optimized solution
n,m = list(map(int,input().split()))
p = [list(map(int,input().split())) for i in range(m)]
q = int(eval(input()))
v = [list(map(int,input().split())) for i in range(q)]
v = v[::-1]
l = [[] for i in range(n+1)]
for pi in p:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
mita = [-1]*(n+1)
tugi = [set() for i in range(n+1)]
iro = [0] *(n+1)
def dfs(x,y,z):
  if iro[x] == 0:
    iro[x] = z
  if mita[x] >=y:
    return
  for i in l[x]:
    if y-1>=0:
      dfs(i,y-1,z)
  mita[x] = y
for ch in v:
  dfs(ch[0],ch[1],ch[2])
for i in range(1,n+1):
  print((iro[i]))
# Original solution
import sys
input = sys.stdin.readline

n, m = list(map(int,input().split()))
nei =[[i] for i in range(n)]

for i in range(m):
    a, b = list(map(int,input().split()))
    a -= 1
    b -= 1
    nei[a].append(b)
    nei[b].append(a)

color = [0 for i in range(n)]
#print(nei)
def paint(v,d,c):
    if color[v] == 0:
        color[v] = c
    if d == 0:
        return
    for i in nei[v]:
        paint(i,d-1,c)

q = int(eval(input()))
vbc = [list(map(int,input().split())) for i in range(q)][::-1]

for i in range(q):
    paint(vbc[i][0]-1,vbc[i][1],vbc[i][2])
    #print(color)

for i in range(n):
    print((color[i]))

# Optimized solution
import sys
input = sys.stdin.readline

n, m = list(map(int,input().split()))
nei =[[i] for i in range(n)]

for i in range(m):
    a, b = list(map(int,input().split()))
    a -= 1
    b -= 1
    nei[a].append(b)
    nei[b].append(a)

color = [0 for i in range(n)]
depth = [-1 for i in range(n)]

def paint(v,d,c,pre):
    if d <= depth[v]:
        return
    depth[v] = d
    if color[v] == 0:
        color[v] = c
    if d == 0:
        return
    for next in nei[v]:
        if next == pre:
            continue
        paint(next,d-1,c,v)

q = int(eval(input()))
vbc = [list(map(int,input().split())) for i in range(q)][::-1]

for i in range(q):
    paint(vbc[i][0]-1,vbc[i][1],vbc[i][2],-1)
    #print(color)


for co in color:
    print(co)
# Original solution
import sys
N,K=list(map(int,input().split()))
A=sorted([int(i) for i in input().split()])
def f(x):
    L=[set() for i in range(N+1)]
    L[0].add(0)
    for i in range(N):
        s=A[i]
        if i==x:
            s=0
        for k in L[i]:
            L[i+1].add(k)
            if k+s<K:
                L[i+1].add(k+s)
    for k in L[N]:
        if k+A[x]>=K:
            return True
    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:
    #print(ma,mi)
    a=(ma+mi)//2
    if f(a):
        ma=a
    else:
        mi=a
print(ma)

# Optimized solution
import sys
N,K=list(map(int,input().split()))
A=sorted([int(i) for i in input().split()])
sa=sum(A)
def f(x):
    if A[x]>=K:
        return True
    L=set()
    L.add(0)
    for i in range(N):
        T=set()
        s=A[i]
        if i==x:
            s=0
        for k in L:
            T.add(k)
            if k+s<K:
                T.add(k+s)
        L=T
    for k in L:
        if k+A[x]>=K:
            return True
    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:
    #print(ma,mi)
    a=(ma+mi)//2
    if f(a):
        ma=a
    else:
        mi=a
print(ma)
# Original solution
N, K = list(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)

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)


# Optimized solution
N, K = list(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)

# あああああああああああああああああああ＼(＾o＾)／
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)
# Original solution
N, K = list(map(int, input().split()))
a = list(map(int, input().split()))
a = sorted(a)

if N == 1:
	if a[0] >= K:
		print((0))
	else:
		print((1))

else:
	def check(i):
		if a[i] >= K:
			return True
		if i == 0:
			b = a[1:]
		elif i == N - 1:
			b = a[:N - 1]
		else:
			b = a[:i] + a[i+1:]
		#print(b)
		#ok = False
		dp = [[False] * K for _ in range(N - 1)]
		if b[0] < K:
			dp[0][b[0]] = True
		if K - a[i] <= b[0] < K:
			return True
		for j in range(1, N - 1):
			for k in range(1, K):
				#if b[j] == K:
				#	return True
				#elif dp[j - 1][k] == True:
				if dp[j - 1][k] == True:
					dp[j][k] = True
				elif k > b[j]:
					if dp[j - 1][k - b[j]] == True:
						dp[j][k] = True

				if dp[j][k] == True and K - a[i] <= k < K:
					return True

		return False


	def bi_search(lower, upper):
		#print(lower, upper)
		mid = (lower + upper) // 2
		#print(mid)
		if mid == 0 and check(mid) == True:
			return 0
		elif mid == N - 2 and check(mid + 1) == False:
			return N
		elif check(mid) == False and check(mid + 1) == True:
			#print("hoge")
			return mid + 1
		elif check(mid) == True:
			return bi_search(lower, mid)
		else:
			return bi_search(mid + 1, upper)


	print((bi_search(0, N - 1)))


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

if N == 1:
	if a[0] >= K:
		print((0))
	else:
		print((1))

else:
	def check(i):
		if a[i] >= K:
			return True
		if i == 0:
			b = a[1:]
		elif i == N - 1:
			b = a[:N - 1]
		else:
			b = a[:i] + a[i+1:]
		#print(b)
		#ok = False
		#dp = [[False] * K for _ in range(N - 1)]
		dp = [False] * K
		#dp[0] = True
		if b[0] < K:
			#dp[0][b[0]] = True
			dp[b[0]] = True
		if K - a[i] <= b[0] < K:
			return True
		for j in range(1, N - 1):

			dp2 = [False] * K
			#if b[j] < K:
				#dp[b[j]] = True
			for k in range(1, K):
				#if b[j] == K:
				#	return True
				#elif dp[j - 1][k] == True:
				if dp[k] == True:
					dp2[k] = True
				
				#elif k > b[j]:
				
				if k >= b[j]:
					#if dp[j - 1][k - b[j]] == True:
					if dp[k - b[j]] == True:
						#dp[j][k] = True
						dp2[k] = True

				#if dp[j][k] == True and K - a[i] <= k < K:
				if dp2[k] == True and K - a[i] <= k:
					return True

			#print(dp)
			dp = dp2

		return False


	def bi_search(lower, upper):
		#print(lower, upper)
		mid = (lower + upper) // 2
		#print(mid)
		if mid == 0 and check(mid) == True:
			return 0
		elif mid == N - 2 and check(mid + 1) == False:
			return N
		elif check(mid) == False and check(mid + 1) == True:
			#print("hoge")
			return mid + 1
		elif check(mid) == True:
			return bi_search(lower, mid)
		else:
			return bi_search(mid, upper)


	print((bi_search(0, N - 1)))
# Original solution
n, k = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    x = a[mi-1]
    if x >= k:
        ba = mi
        continue
    #print(mi)
    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]

    #print(dp)
    if sum(dp[k-x:k]):
        ba = mi
    else:
        fr = mi

print(fr)

# Optimized solution
import sys

n, k = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    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)
# Original solution
from bisect import bisect_left, bisect_right

def solve():
    N, K = list(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):
        isFounds = [False] * K
        isFounds[0] = True
        for i, B in enumerate(Bs):
            if i == x: continue
            for s in reversed(list(range(K-B))):
                if isFounds[s]:
                    isFounds[s+B] = True
        return any(isFounds[K-Bs[x]:])

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

    print(ok)


solve()


# Optimized solution
from bisect import bisect_left, bisect_right

def solve():
    N, K = list(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()
# Original solution
from bisect import bisect_left, bisect_right
from itertools import accumulate

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

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

    setSums = [{0}]
    setSum = {0}
    for B in Bs:
        for s in list(setSum):
            if s+B < K:
                setSum.add(s+B)
        setSums.append(setSum.copy())
    setSumRevs = [{0}]
    setSum = {0}
    for B in reversed(Bs):
        for s in list(setSum):
            if s+B < K:
                setSum.add(s+B)
        setSumRevs.append(setSum.copy())
    setSumRevs.reverse()

    def isOK(x):
        B = Bs[x]
        numRevs = [0] * K
        for s in setSumRevs[x+1]:
            numRevs[s] = 1
        accNumRevs = list(accumulate([0]+numRevs))
        for s in setSums[x]:
            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()


# Optimized solution
from bisect import bisect_left, bisect_right
from itertools import accumulate

def solve():
    N, K = list(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()
# Original solution
import bisect


def preliminary(k, aaa):
    dp = [False] * k
    dp[0] = True
    curr_max = 0
    fwd = []
    for a in aaa:
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        fwd.append(dp[:])
        curr_max += a

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    bwd = []
    for a in reversed(aaa):
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        bwd.append([i for i, v in enumerate(dp) if v][1:])
        curr_max += a
    bwd.reverse()

    dummy = [False] * k
    dummy[0] = True
    fwd.append(dummy)
    bwd.append([])

    return fwd, bwd


def get_judge(k, aaa):
    fwd, bwd = preliminary(k, aaa)
    cache = [None] * k

    def judge(m):
        am = aaa[m]
        if cache[am] is None:
            dp = fwd[m - 1]
            ndp = dp[:]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        ndp[i + j] = True
            cache[am] = any(ndp[-am:])
        return cache[am]

    return judge


def solve(k, aaa):
    if sum(aaa) < k:
        return n

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

    judge = get_judge(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        if judge(m):
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


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


# Optimized solution
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 = list(map(int, input().split()))
aaa = list(map(int, input().split()))
aaa.sort()

print((solve(k, aaa)))
# Original solution
n,k = list(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)

# Optimized solution
n,k = list(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)
# Original solution
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: list(map(int, stdin.readline().split()))
nl = lambda: list(map(int, stdin.readline().split()))


def solve():
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    
    def trans(v):
    	l = [0] * (k + 1)
    	for i in range(k + 1):
        	l[i] = (v & 1)
        	v >>= 1
    	return l
  
    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
        lc = trans(lef[mid])
        rc = trans(rig[mid])
        # print(a[mid], lc, rc)
        rcs = [0] * (k + 2)
        for i in range(k + 1):
            rcs[i + 1] = rcs[i] + rc[i]
        for i in range(k + 1):
            if lc[i] and rcs[k - i] - rcs[max(k - a[mid] - i, 0)] > 0:
                ng = mid
                break
        else:
            ok = mid
    print((ok + 1))

if __name__ == '__main__':
    solve()

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