Suppose we have fixed the choice of songs to songs \(j_1,j_2,\ldots,j_k\), sorted in descending order of the numbers of the idols required \((B_{j_1}\geq B_{j_2}\geq \cdots \geq B_{j_k} )\). We claim that one can choose an assignment of idols to these songs subject to the limits of performance count for each dancer if and only if:

for all \(1\leq k'\leq k\), \(\displaystyle \sum_{i=1}^N \min(A_i,k')\geq \sum_{j'=1}^{k'} B_{j_{j'}}. \)

This is obviously necessary because, if this is violated for some \(k'\), we are short of the total number of idols required to perform songs \(j_1,j_2,\ldots,j_{k'}\).
Now we show that is is sufficient too, by induction on \(k\). For \(k=1\), it is obvious that assignment is possible, so assume \(k\geq 2\). We pick \(B_{j_1}\) idols with largest values \(A_i\) and let them perform in song \(j_1\). Now the idols’ remaining capacity \(A'_i\) (\(= A_i-1\) if picked for song \(j_1\) and \(A_i\) otherwise) satisfies either \(\displaystyle \sum_{i=1}^N \min(A'_i,k'-1)= \sum_{i=1}^N \min(A_i,k')-B_1\) (if no \(i\) satisfies \(A_i=A'_i\geq k'\)) or \(\displaystyle \sum_{i=1}^N \min(A'_i,k'-1)\geq B_1(k'-1)\) (if some \(i\) satisfies \(A_i=A'_i\geq k'\); in any case, \(\displaystyle \sum_{i=1}^N \min(A'_i,k'-1)\geq \sum_{j'=2}^{k'} B_{j_{j'}}\). By assumption of the induction, there is an assignment for songs \(j_2,j_3,\ldots,j_k\) subject to their capacities, which implies it is sufficient for \(k\).

Next, we consider how to find the maximum total excitement subject to the condition above. We assume that the songs are sorted in descending order of \(B_i\), so that \(B_1\geq B_2\geq\cdots\geq B_M\). Here, note that \(R_{k'}=\sum_{i=1}^N \min(A_i,k')\) is independent of choice of songs.

This can be computed using a dynamic programming (DP).
Define \(dp[j][k][s]\) \((0\leq k\leq j\leq M, 0\leq s\leq NM)\) as the maximum possible total excitement when choosing \(k\) songs out of songs \(1,2,\ldots,j\) (sorted) subject to the following two conditions (or \(-\infty\) if such choice is impossible):

• The chosen songs \(x_1, x_2,\ldots,x_k\) \((1\leq x_1<x_2<\cdots<x_k\leq j)\) satisfy \(B_{x_1}+B_{x_2}+\cdots+B_{x_k}=s\).

• \(B_{x_1}+B_{x_2}+\cdots+B_{x_k'}\leq R_{k'}\) for all \(1\leq k'\leq k\).

The value \(dp[0][k][s]\) is \(0\) is \(k=s=0\) and \(-\infty\) otherwise. For \(j>0\), we consider cases where we do or do not choose song \(j\). The transition is:

• \(dp[j][k][s]=-\infty\) if \(s>R_k\).
• otherwise, \(dp[j][k][s]=dp[j-1][k][s]\) if \(s<B_j\).
• otherwise, \(dp[j][k][s]=\max(dp[j-1][k][s],dp[j-1][k-1][s-B_j]+C_j)\).

The answer can be found as \(\displaystyle\max_{0\leq k\leq M}\max_{0\leq s\leq NM} dp[M][k][s]\). The computational complexity is \(O(NM^3)\); thanks to a small constant factor, this is fast enough under the constraints of this problem.
Therefore, the problem has been solved.

Sample code in C++: