Buggy python submission (verdict: Runtime Error):
import bisect


def preliminary(k, aaa):
    dp = [False] * k
    dp[0] = True
    curr_max = 0
    fwd = {}
    pa = aaa[0]
    pdp, ppdp = dp[:], None
    for a in aaa:
        if pa != a:
            fwd[pa] = ppdp
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        curr_max += a
        pa = a
        ppdp = pdp
        pdp = dp[:]
    fwd[pa] = ppdp

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    bwd = {}
    pa = 0
    pdp = []
    for a in reversed(aaa):
        if pa != a:
            bwd[a] = [i for i, v in enumerate(pdp) if v][1:]
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        curr_max += a
        pa = a
        pdp = dp[:]

    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[am]
            ndp = dp[:]
            for i in bwd[am]:
                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 = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))


Fixed submission:
import bisect


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

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


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

print(solve(k, aaa))

Buggy python submission (verdict: Time Limit Exceeded):
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 = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))


Fixed submission:
import bisect


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

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


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

print(solve(k, aaa))

Buggy python submission (verdict: Runtime Error):
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.copy())
        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]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        dp[i + j] = True
            cache[am] = any(dp[-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 = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))


Fixed submission:
import bisect


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

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


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

print(solve(k, aaa))

Buggy python submission (verdict: Runtime Error):
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.copy())
        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]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        dp[i + j] = True
            cache[am] = any(dp[-am:])
        return cache[am]

    return judge


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

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

# n = 5000
# k = 5000
# aaa = list(range(1, n + 1))

print(solve(k, aaa))


Fixed submission:
import bisect


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

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


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

print(solve(k, aaa))

Buggy python submission (verdict: Runtime Error):
import bisect

import numpy as np
from scipy.ndimage.interpolation import shift


def preliminary(k, aaa):
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    fwd = []
    for a in aaa:
        dp |= shift(dp, a)
        fwd.append(dp.copy())

    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    bwd = []
    for a in reversed(aaa):
        dp |= shift(dp, a)
        bwd.append(np.where(dp)[0])
    bwd.reverse()

    fwd.append(np.zeros(k, np.uint8))
    bwd.append([0])

    return fwd, bwd


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

    fwd, bwd = preliminary(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        dp = fwd[m - 1]
        for i in bwd[m + 1][1:]:
            dp |= shift(dp, i)
        if dp[-aaa[m]:].any():
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


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


Fixed submission:
import bisect


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

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


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

print(solve(k, aaa))

Buggy python submission (verdict: Runtime Error):
import bisect
import numpy as np
from scipy.ndimage.interpolation import shift


def judge(e):
    ae = aaa[e]
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    for i, a in enumerate(aaa):
        if i == e:
            continue
        dp |= shift(dp, a)
    return dp[-ae:].any()


def solve(k, aaa):
    l = 0
    r = bisect.bisect_left(aaa, k) - 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 = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(k, aaa))


Fixed submission:
import bisect


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

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


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

print(solve(k, aaa))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import numpy as np
from scipy.ndimage.interpolation import shift


def judge(e):
    ae = aaa[e]
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    for i, a in enumerate(aaa):
        if i == e:
            continue
        dp |= shift(dp, a)
    return dp[-ae:].any()


def solve(k, aaa):
    l = 0
    r = bisect.bisect_left(aaa, k) - 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 = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(k, aaa))


Fixed submission:
import bisect


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

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


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

print(solve(k, aaa))

Buggy python submission (verdict: Time Limit Exceeded):
def is_needed(i):
    dp = [False] * k
    dp[0] = True
    lm = 0
    for j, w in enumerate(aa):
        if i == j:
            continue
        set_lm = False
        for l in range(min(k - w - 1, lm), -1, -1):
            if dp[l]:
                dp[l + w] = True
                if not set_lm:
                    lm = l + w
                    set_lm = True
    return any(dp[k - aa[i]:])


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

l, h = 0, n - 1
while l <= h:
    c = (l + h) // 2
    if is_needed(c):
        h = c - 1
    else:
        l = c + 1
print(l)


Fixed submission:
import bisect


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

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


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

print(solve(k, aaa))

Buggy python submission (verdict: Time Limit Exceeded):
def is_needed(i):
    dp = [False] * k
    dp[0] = True
    for j, w in enumerate(aa):
        if i == j:
            continue
        for l in range(k - 1, w - 1, -1):
            if dp[l - w]:
                dp[l] = True
    return any(dp[k - aa[i]:])


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

l, h = 0, n - 1
while l <= h:
    c = (l + h) // 2
    if is_needed(c):
        h = c - 1
    else:
        l = c + 1
print(l)


Fixed submission:
import bisect


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

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


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

print(solve(k, aaa))