← 返回题目列表

AtCoder · arc070_b

D. 不需要

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

AtCoDeer 鹿有 N 卡片上写有正整数。上的号码 i第一张卡 (1≤i≤N) is a_i。 因为他喜欢大数字,所以他称卡片的子集为 好 当子集中卡片上写的数字之和为 K 或更大。

然后,对于每张卡 i,他判断是否是 不必要 或不,如下:

  • 如果,对于包含卡的卡的任何好的子集 i,消除卡牌可获得的套装 i 离子集也不错,卡 i 是不必要的。
  • 否则,卡 i 不是不必要的。

找出不需要的牌的数量。在这里,他独立地判断每张牌,并且不会丢弃那些被证明是不必要的牌。

约束

  • 所有输入值均为整数。
  • 1≤N≤5000
  • 1≤K≤5000
  • 1≤a_i≤10^9 (1≤i≤N)

部分分数

  • 300 通过满足以下条件的测试集将获得积分 N,K≤400.

输入

输入由标准输入按以下格式给出:

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,一套很好的{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