题目描述

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

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

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

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

输入格式

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

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

输出格式

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

题目大意

给出一个由N个整数构成的集合和一个整数K，若该集合中的的非空子集和大于等于K，则称该子集为优秀的集合

若去掉一个数不会对优秀集合的个数产生影响，则称该数字为“可有可无的数字”
请求出在N个数中“可有可无的数字”个数

3 6
1 4 3

1

5 400
3 1 4 1 5

5

6 20
10 4 3 10 25 2

3

提示

制約

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

部分点

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

Sample Explanation 1

よい集合は {$2,3$} と {$1,2,3$} の二つです。 カード $1$ を含むよい集合は {$1,2,3$} しかなく、これから $1$ を取り除いた {$2,3$} もよい集合なので、カード $1$ は不必要です。 また、よい集合である {$2,3$} から $2$ を取り除いた集合 {$3$} はよい集合ではないため、カード $2$ は不必要ではありません。 カード $3$ も同様に不必要ではないため、答えは $1$ です。

Sample Explanation 2

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