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

stdin = sys.stdin

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


def solve():
    n, k = 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()

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

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

stdin = sys.stdin

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


def solve():
    n, k = nm()
    a = nl()
    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 = lef[mid]
      rc = rig[mid]
      cov = ((1 << k) - 1) ^ ((1 << max(k - a[mid], 0)) - 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)
    return

solve()


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

Buggy python submission (verdict: Time Limit Exceeded):
n, k = 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)

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

Buggy python submission (verdict: Time Limit Exceeded):
n, k = 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 = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << max(k - a[mid], 0)) - 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)

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

Buggy python submission (verdict: Time Limit Exceeded):
n, k = 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 = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << max(k - a[mid], 0)) - 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)

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

Buggy python submission (verdict: Runtime Error):
n, k = 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 = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k+1):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)

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

Buggy python submission (verdict: Time Limit Exceeded):
n, k = 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)

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

Buggy python submission (verdict: Runtime Error):
_,k = map(int,input().split())
a = list(filter(lambda x:x<k,list(map(int,input().split()))))
n = len(a)
a.sort(reverse=True)
dpf = [[False]*k for _ in range(n)] 
dpb = [[False]*k for _ in range(n)] 
dpf[0][0] = True
dpb[-1][0] = True
for i in range(n-1):
  wf = a[i]
  wb = a[-(i+1)]
  for j in range(k):
    if dpf[i][j]:
      dpf[i+1][j] = True
      if j+wf < k:
        dpf[i+1][j+wf] = True
    if dpb[-(i+1)][j]:
      dpb[-(i+2)][j] = True
      if j+wb < k:
        dpb[-(i+2)][j+wb] = True
        
def check(v):
  w = a[v]
  im = [0]*(k+1)
  lf = dpf[v]
  lb = dpb[v]
  for i in range(k):
    if lb[i]:
      if k-i <= 0:
        continue
      im[max(k-w-i,0)] += 1
      im[k-i] -= 1
  if lf[0] and im[0]>0:
    return False
  for i in range(1,k):
    im[i] += im[i-1]
    if lf[i] and im[i]>0:
      return False
  return True
 
ng = -1
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  if check(mid):
    ok = mid
  else:
    ng = mid
print(n-ok)


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

Buggy python submission (verdict: Runtime Error):
_,k = map(int,input().split())
a = list(filter(lambda x:x<k,list(map(int,input().split()))))
n = len(a)
a.sort(reverse=True)
dpf = [[False]*k for _ in range(n)] 
dpb = [[False]*k for _ in range(n)] 
dpf[0][0] = True
dpb[0][0] = True
for i in range(n-1):
  wf = a[i]
  wb = a[-(i+1)]
  for j in range(k):
    if dpf[i][j]:
      dpf[i+1][j] = True
      if j+wf < k:
        dpf[i+1][j+wf] = True
    if dpb[i][j]:
      dpb[i+1][j] = True
      if j+wb < k:
        dpb[i+1][j+wb] = True
        
def check(v):
  w = a[v]
  im = [0]*(k+1)
  lf = dpf[v]
  lb = dpb[n-v-1]
  for i in range(k):
    if lb[i]:
      if k-i <= 0:
        continue
      im[max(k-w-i,0)] += 1
      im[k-i] -= 1
  if lf[0] and im[0]>0:
    return False
  for i in range(1,k):
    im[i] += im[i-1]
    if lf[i] and im[i]>0:
      return False
  return True
 
ng = -1
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  if check(mid):
    ok = mid
  else:
    ng = mid
print(n-ok)


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

Buggy python submission (verdict: Time Limit Exceeded):
def main():
  n,k = map(int,input().split())
  a = list(filter(lambda x:x<k,list(map(int,input().split()))))
  n = len(a)
  a.sort(reverse=True)
  ng = -1
  ok = n
  while ok-ng > 1:
    mid = (ok+ng)//2
    dp = [False]*(k+1)
    dp[0] = True
    f = 0
    for j in range(n):
      if j == mid:
        continue
      w = a[j]
      for i in range(k,w-1,-1):
        if dp[i-w]:
          dp[i] = True
          if k-a[mid] <= i < k:
            ng = mid
            f = 1
            break
      if f:
        break
    else:
      ok = mid
      
  print(n-ok)

if __name__ == "__main__":
  main()
  

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

Buggy python submission (verdict: Runtime Error):
def main():
  n,k = map(int,input().split())
  a = list(filter(lambda x:x<k,list(map(int,input().split()))))
  n = len(a)
  a.sort(reverse=True)
  ng = -1
  ok = n
  while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  f = 0
  for j in range(n):
    if j == mid:
      continue
    w = a[j]
    for i in range(k,w-1,-1):
      if dp[i-w]:
        dp[i] = True
        if k-a[mid] <= i < k:
          ng = mid
          f = 1
          break
    if f:
      break
  else:
    ok = mid
      
  print(n-ok)

if __name__ == "__main__":
  main()
  

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

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
a = list(filter(lambda x:x<k,list(map(int,input().split()))))
n = len(a)
a.sort(reverse=True)
ng = -1
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  f = 0
  for j in range(n):
    if j == mid:
      continue
    w = a[j]
    for i in range(k,w-1,-1):
      if dp[i-w]:
        dp[i] = True
        if k-a[mid] <= i < k:
          ng = mid
          f = 1
          break
    if f:
      break
  else:
    ok = mid
      
print(n-ok)


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

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
a = list(filter(lambda x:x<k,list(map(int,input().split()))))
n = len(a)
a.sort(reverse=True)
ng = -1
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  f = 0
  for j in range(n):
    if j == mid:
      continue
    w = a[j]
    for i in range(k,w-1,-1):
      if dp[i-w]:
        dp[i] = True
        if k-a[mid] <= i < k:
          ng = mid
          f = 1
          break
    if f:
      break
  else:
    ok = mid
      
print(n-ok)


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

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
hi = -1
lo = n
while lo-hi>1:
  mid = (lo+hi)//2
  if a[mid] >= k:
    hi = mid
  else:
    lo = mid
ng = hi
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  for j in range(n):
    if j == mid:
      continue
    w = a[j]
    for i in range(k,w-1,-1):
      dp[i] |= dp[i-w]
  if any(dp[k-a[mid]:k]):
    ng = mid
  else:
    ok = mid
print(n-ok)


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

Buggy python submission (verdict: Time Limit Exceeded):
def main():
  n,k = map(int,input().split())
  a = list(map(int,input().split()))
  a.sort(reverse=True)
  hi = -1
  lo = n
  while lo-hi>1:
    mid = (lo+hi)//2
    if a[mid] >= k:
      hi = mid
    else:
      lo = mid
  ng = hi
  ok = n
  while ok-ng > 1:
    mid = (ok+ng)//2
    dp = [False]*(k+1)
    dp[0] = True
    for j in range(n):
      if j == mid:
        continue
      w = a[j]
      for i in range(k,w-1,-1):
        dp[i] |= dp[i-w]
    if any(dp[k-a[mid]:k]):
      ng = mid
    else:
      ok = mid
  print(n-ok)
  return
if __name__ == "__main__":
  main()

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

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
hi = -1
lo = n
while lo-hi>1:
  mid = (lo+hi)//2
  if a[mid] >= k:
    hi = mid
  else:
    lo = mid
ng = hi
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  for j in range(n):
    if j == mid:
      continue
    w = a[j]
    for i in range(k,w-1,-1):
      dp[i] |= dp[i-w]
  if any(dp[k-a[mid]:k]):
    ng = mid
  else:
    ok = mid
print(n-ok)

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

Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
hi = -1
lo = n
while lo-hi>1:
  mid = (lo+hi)//2
  if a[mid] >= k:
    hi = mid
  else:
    lo = mid
ng = hi
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  f = 1
  for j in range(n):
    if j == mid:
      f = 0
      continue
    w = a[j]
    new = dp.copy()
    for i in range(k-w+1):
      new[i+w] |= dp[i]
    dp = new
  if any(dp[k-a[mid]:k]):
    ng = mid
  else:
    ok = mid
print(n-ok)


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

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
hi = -1
lo = n
while lo-hi>1:
  mid = (lo+hi)//2
  if a[mid] >= k:
    hi = mid
  else:
    lo = mid
ng = hi
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  f = 1
  for j in range(n):
    if j == mid:
      f = 0
      continue
    w = a[j]
    new = dp.copy()
    for i in range(k-w+1):
      new[i+w] |= dp[i]
    dp = new
  if any(dp[k-a[mid]:k]):
    ng = mid
  else:
    ok = mid
print(n-ok)

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