F - Team Making

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

QUPC 2022 九州大学オンサイトには N 人の参加者がいます。i 番目の参加者の AtCoder のレーティングは 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