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

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.

Examples

Input

3 6
1 4 3

Output

1

Input

5 400
3 1 4 1 5

Output

5

Input

6 20
10 4 3 10 25 2

Output

3
Solve the task in PYTHON3.
 Can you provide a Python code to find the number of the unnecessary cards?
assistant
#Here is Python code to find the number of the unnecessary cards.

# -*- coding: utf-8 -*-
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))

if __name__ == '__main__':
    main()