← 返回题目列表

AtCoder · qupc2018_f

F. 团队建设

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

配点 : 600 点

問題文

QUPC 2022 九州大学现场有 N 名参与者。i 号参与者的 AtCoder ore 评分是 A_i 。

N 人的参与者将根据以下条件分成几个团队。

  • 每个团队的×是 1 人以上 3 人以下
  • 每个团队所属的参与者的 AtCoder 等级平均值是 K 以下
  • 无论 AtCoder 等级值如何,1 都可以以 人的团队形式参与

请求出满足条件的团队分法有多少种。在该问题的否定下,答案保证不超过 10^{18} 。

制約

  • 1 \leq N \leq 18
  • 0 \leq K \leq 4208
  • 0 \leq A_i \leq 4208
  • 输入全部为整数

入力

输入将以以下格式从标准输入提供。

N K
A_1 A_2 ... A_N

出力

请输出满足条件的团队组合数。


入力例 1

3 2000
1999 2000 2001

出力例 1

4

3 不超过 人的团队组合方式如下 5 种,以上的 4 种满足条件。

  • 1 第 番参与者单独的团队、2 第 番参与者单独的团队、3 第 番参与者单独的团队
  • 1 第 番参与者与 2 第 番参与者与 3 第 番参与者的 3人团队
  • 1 第 番参与者与 2 第 番参与者的 2 人团队、3 第 番参与者单独的团队
  • 1 第 番参与者与 3 第 番参与者的 2 人团队、2 第 番参与者单独的团队
  • 2 第 番参与者与 3 第 番参与者的 2 人团队、1 第 番参与者单独的团队

入力例 2

4 2000
2500 3000 1000 2000

出力例 2

6

入力例 3

12 2000
3092 2432 2312 1867 1794 1730 1670 1523 1495 1299 1169 1024

出力例 3

297042