分数: 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