[ABC056D] No Need

给出一个由 $N$ 个整数构成的集合和一个整数 $K$，若该集合中的的非空子集和大于等于 $K$，则称该子集为优秀的集合 若所有包含这个数的优秀子集去掉该数后仍然是优秀集合，则称该数字为“可有可无的数字”。 请求出在 $N$ 个数中“可有可无的数字”个数。

[problemUrl]: https://atcoder.jp/contests/abc056/tasks/arc070_b シカのAtCoDeerくんは正整数が書かれたカードを $ N $ 枚持っています。$ i(1≦i≦N) $ 枚目に書かれている数は $ a_i $ です。 AtCoDeerくんは大きい数が好きなので、カードに書かれた数の総和が $ K $ 以上になるようなカードの部分集合を*よい集合*と呼びます。 そして、各カード $ i $ に対して、そのカードが*不必要*かどうかを次のように判定します。 - 「カード $ i $ を含む任意の*よい集合*に対して、その集合からカード $ i $ を除いたものも*よい集合*」 ならカード $ i $ は*不必要* - それ以外の場合は、*不必要*でない 不必要なカードの枚数を求めてください。ただし、それぞれの判定は独立に行われ、不必要だからと言ってカードが途中で捨てられたりすることはありません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ a_1 $ $ a_2 $ ... $ a_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 この場合よい集合は存在しないため、全てのカードは不必要となります。