\(A_1, A_2,\dots,A_N\) を降順にソートしても答えは変わりません。そのため以下 \(A_1\ge A_2\ge\dots\ge A_N\) とします。

\(1\le x_1<x_2<\dots<x_{\left\vert S\right\vert}\le N\) を満たす整数 \(x_1,x_2,\dots,x_{\left\vert S\right\vert}\) を用いて \(S=\{x_1,x_2,\dots,x_{\left\vert S\right\vert}\}\) と表し、 \(f(S)=\{x_1,x_2,\dots,x_{\left\vert S\right\vert-k}\}\) と定めます。このとき、 \(T=f(S)\) は \(\sum_{i\in T} A_i\) を最大化するものの一つです。 そのため、 \(S\) が満たすべき条件は以下のように言い換えられます。

• \(\sum_{i\in f(S)} A_i \ge M\)

条件を満たす \(S\) の個数は、 \(\{1,2,\dots,N\}\) の部分集合 \(T\) すべてについての \(f(S)=T\) を満たす \(S\) の個数の総和と等しいです。

\(k\) を固定し \(T=\{x_1,x_2,\dots,x_{\left\vert T\right\vert}\}\) としたとき、 \(f(S)=T\) を満たす \(S\) は \({}_{N-x_{\left\vert T\right\vert}} \mathrm{ C }_k\) 個あります。

よって、 \(B_i\) を \(x_{\left\vert T\right\vert}=i\) を満たす \(T\) の総数と定めたとき、答えは \(\sum_{i=1}^{N}B_i\times {}_{N-i} \mathrm{ C }_k\) です。 そのため \(B_1,\dots,B_N\) が求められていれば \(k=0,1,\dots,N\) について全体で \(\Theta(N^2)\) 時間で答えを求められます。（ \({}_{n} \mathrm{ C }_k\) はパスカルの三角形を用いると \(\Theta(N^2)\) 時間で求められます。）

\(B_1,B_2,\dots,B_N\) は、 \(\mathrm{dp}[i][j]\) を \(\{1,2,\dots,i\}\) の部分集合 \(T\) のうち \(\sum_{i\in T} A_i < j\) を満たすものの総数として dp を行うと \(B_i=2^{i-1}-\mathrm{dp}[i-1][M-A_i]\) であり、求めることができます。

時間計算量は \(\Theta(NM+N^2)\) です。

Bouns: \(N,M,\sum A \le 2 \times 10^5\)