問題文

シカのAtCoDeerくんは正整数が書かれたカードを $N$ 枚持っています。$i(1≦i≦N)$ 枚目に書かれている数は $a_i$ です。 AtCoDeerくんは大きい数が好きなので、カードに書かれた数の総和が $K$ 以上になるようなカードの部分集合を_よい集合_と呼びます。

そして、各カード $i$ に対して、そのカードが_不必要_かどうかを次のように判定します。

• 「カード $i$ を含む任意の_よい集合_に対して、その集合からカード $i$ を除いたものも_よい集合_」 ならカード $i$ は_不必要_
• それ以外の場合は、_不必要_でない

不必要なカードの枚数を求めてください。ただし、それぞれの判定は独立に行われ、不必要だからと言ってカードが途中で捨てられたりすることはありません。

制約

• 入力は全て整数
• $1≦N≦5000$
• $1≦K≦5000$
• $1≦a_i≦10^9 (1≦i≦N)$

部分点

• $N,K≦400$ を満たすデータセットに正解した場合は、部分点として $300$ 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $a_1$ $a_2$ ... $a_N$

出力

不必要なカードの枚数を出力せよ。

入力例 1

3 6
1 4 3

出力例 1

1

よい集合は {$2,3$} と {$1,2,3$} の二つです。

カード $1$ を含むよい集合は {$1,2,3$} しかなく、これから $1$ を取り除いた {$2,3$} もよい集合なので、カード $1$ は不必要です。

また、よい集合である {$2,3$} から $2$ を取り除いた集合 {$3$} はよい集合ではないため、カード $2$ は不必要ではありません。

カード $3$ も同様に不必要ではないため、答えは $1$ です。

入力例 2

5 400
3 1 4 1 5

出力例 2

5

この場合よい集合は存在しないため、全てのカードは不必要となります。

入力例 3

6 20
10 4 3 10 25 2

出力例 3

3