AtCoder Regular Contest 070

D - No Need


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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

Submit提出する