AT_qupc2018_f.Team Making

QUPC 2022 九州大学现场赛有 $N$ 名参赛者。第 $i$ 位参赛者的 AtCoder 等级为 $A_i$。

请将 $N$ 名参赛者分成若干个团队，要求满足以下条件：

• 每个团队的人数不少于 $1$ 人且不超过 $3$ 人；
• 每个团队内所有成员的 AtCoder 等级的平均值不超过 $K$；
• 无论 AtCoder 等级如何，允许某人单独组成一个团队。

请计算满足条件的分组方案总数。在本题的约束下，答案不会超过 $10^{18}$。

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

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出满足条件的分组方案总数。

限制条件

• $1 \leq N \leq 18$
• $0 \leq K \leq 4208$
• $0 \leq A_i \leq 4208$
• 所有输入均为整数

样例解释 1

将 $3$ 人分组的所有方式如下，共有 $5$ 种，其中前 $4$ 种满足条件。

• 第 $1$ 人单独成队，第 $2$ 人单独成队，第 $3$ 人单独成队
• 第 $1$ 人、第 $2$ 人、第 $3$ 人组成一个 $3$ 人团队
• 第 $1$ 人和第 $2$ 人组成 $2$ 人团队，第 $3$ 人单独成队
• 第 $1$ 人和第 $3$ 人组成 $2$ 人团队，第 $2$ 人单独成队
• 第 $2$ 人和第 $3$ 人组成 $2$ 人团队，第 $1$ 人单独成队

由 ChatGPT 4.1 翻译