/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 600 点
問題文
シカの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
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≤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)
Partial Score
- 300 points will be awarded for passing the test set satisfying N,K≤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.
Sample Input 1
3 6 1 4 3
Sample Output 1
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.
Sample Input 2
5 400 3 1 4 1 5
Sample Output 2
5
In this case, there is no good set. Therefore, all the cards are unnecessary.
Sample Input 3
6 20 10 4 3 10 25 2
Sample Output 3
3