Score : $600$ points

Problem Statement

AtCoDeer the deer has $N$ cards with positive integers written on them. The number on the $i$-th card $(1 \leq i \leq 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 \leq N \leq 5000$
• $1 \leq K \leq 5000$
• $1 \leq a_i \leq 10^9 (1 \leq i \leq N)$

Partial Score

• $300$ points will be awarded for passing the test set satisfying $N,K \leq 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.

3 6
1 4 3

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$.

5 400
3 1 4 1 5

5

In this case, there is no good set. Therefore, all the cards are unnecessary.

6 20
10 4 3 10 25 2

3