AT_arc070_b.[ABC056D] No Need

シカ的 AtCoDeer 君拥有 $N$ 张写有正整数的卡片。其中，第 $i$ 张卡片上写着数字 $a_i$。AtCoDeer 君喜欢大的数字，因此将所有卡片中数字总和不小于 $K$ 的部分集合称为“好集合”。

对于每一张卡片 $i$，判断该卡片是否“不必要”，规则如下：

• 对于任意包含卡片 $i$ 的“好集合”，如果将该集合去掉卡片 $i$ 后，仍然是“好集合”，那么卡片 $i$ 被认为“不必要”。
• 否则，认为卡片 $i$ 是“必要”的（不是“不必要”）。

请你计算不必要的卡片数量。每张卡片独立判定，“不必要”的卡片不会在判定过程中被丢弃。

输入按以下格式从标准输入读入。

$N$ $K$ $a_1$ $a_2$ ... $a_N$

输出不必要卡片的数量。

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 5000$。
• $1 \leq K \leq 5000$。
• $1 \leq a_i \leq 10^9 \quad (1 \leq i \leq N)$。

部分得分

• 如果能通过满足 $N,K\leq 400$ 的数据集，可以获得部分得分 $300$ 分。

样例解释 1

“好集合”为 {$2,3$} 和 {$1,2,3$} 这两个。包含卡片 $1$ 的“好集合”只有 {$1,2,3$}，从中去掉 $1$ 得到 {$2,3$}，它也是“好集合”，所以卡片 $1$ 是“不必要”的。另一方面，“好集合”{$2,3$} 去掉 $2$ 得到 {$3$}，它不是“好集合”，所以卡片 $2$ 不是“不必要”的。卡片 $3$ 同理也不是“不必要”的，因此答案是 $1$。

样例解释 2

这种情况下“好集合”不存在，所以所有卡片都被认为是不必要的。

由 ChatGPT 5 翻译