まず、任意の曲の選び方について、選んだ曲が 踊る必要のある人数が多い順に 曲 \(j_1,j_2,\ldots,j_k\) \((B_{j_1}\geq B_{j_2}\geq \cdots \geq B_{j_k} )\) であるとすると、それぞれのアイドルが踊れる回数を超えないように、 それぞれの曲で踊るアイドルを選ぶことができる必要十分条件は次の通りです。

任意の \(1\leq k'\leq k\) について、

\[ \displaystyle \sum_{i=1}^N \min(A_i,k') \geq \displaystyle \sum_{j'=1}^{k'} B_{j_{j'}} \]

が成り立つ。

これが必要条件となっていることは、もしある \(k'\) でみたされなかったとすると、曲 \(j_1,j_2,\ldots,j_{k'}\) で踊るアイドルの（のべ）人数が足りなくなる事から明らかです。
一方で、\(k\) についての数学的帰納法でこれが十分条件であることもわかります。\(k=1\) のとき踊るアイドルを割り当てられることは明らかです。\(k\geq 2\) のとき、曲 \(j_1\) に \(A_i\) が大きい順に踊るアイドルを割り当てたとすると、任意の \(2\leq k'\leq k\) について、それぞれのアイドルが踊れる残り回数 \(A'_i\)（\(=\)曲 \(j_1\) に割り当てられたならば \(A_i-1\), そうでないならば \(A'_i\)）として、\(\displaystyle \sum_{i=1}^N \min(A'_i,k'-1)= \sum_{i=1}^N \min(A_i,k')-B_1\) （\(A_i=A'_i\geq k'\) となるような \(i\) が存在しない場合）または \(\displaystyle \sum_{i=1}^N \min(A'_i,k'-1)\geq B_1(k'-1)\) （\(A_i=A'_i\geq k'\) となるような \(i\) が存在する場合）が成り立ち、いずれの場合も \(\displaystyle \sum_{i=1}^N \min(A'_i,k'-1)\geq \sum_{j'=2}^{k'} B_{j_{j'}}\) となるため、帰納法の仮定から残り回数の条件をみたすように曲 \(j_2,j_3,\ldots,j_k\) にアイドルを割り当てる方法が存在し、特に \(k\) のときも十分条件となっていることがわかります。

さて、上記の条件をみたすように選ぶときに盛り上がりの総和の最大値を求める方法について考えます。まず、曲は \(B_i\) について降順にソートして考えます。すなわち、一般に \(B_1\geq B_2\geq\cdots\geq B_M\) が成り立っているとします。また、\(1\leq k'\leq M\) について、\(R_{k'}=\sum_{i=1}^N \min(A_i,k')\) は曲の選び方によらないことに注意します。

次のような動的計画法を考えます。
\(dp[j][k][s]\) \((0\leq k\leq j\leq M, 0\leq s\leq NM)\) を、「（ソート後の）曲 \(1,2,\ldots,j\) までのうち \(k\) 曲を、次の \(2\) つの条件をみたすように選んだ時に、選ばれた曲の盛り上がりの総和としてあり得る最大値（選び方が存在しなければ \(-\infty\) ）」で定義します。

• 選ばれた曲を \(x_1, x_2,\ldots,x_k\) \((1\leq x_1<x_2<\cdots<x_k\leq j)\) とすると、\(B_{x_1}+B_{x_2}+\cdots+B_{x_k}=s\) である。

• 任意の \(1\leq k'\leq k\) について、\(B_{x_1}+B_{x_2}+\cdots+B_{x_{k'}}\leq R_{k'}\) が成り立つ。

\(dp[0][k][s]\) の値は \(k=s=0\) のときのみ \(0\) で、それ以外ならば \(-\infty\) となります。 \(j>0\) のとき、曲 \(j\) を選ぶかどうかで、

• \(s>R_k\) ならば \(dp[j][k][s]=-\infty\)
• そうでなく \(s<B_j\) のとき、\(dp[j][k][s]=dp[j-1][k][s]\)
• そうでないとき、\(dp[j][k][s]=\max(dp[j-1][k][s],dp[j-1][k-1][s-B_j]+C_j)\)

と遷移することができます。 答えは、\(\displaystyle\max_{0\leq k\leq M}\max_{0\leq s\leq NM} dp[M][k][s]\) でもとめることができます。計算量は \(O(NM^3)\) で、今回の制約下では定数倍が早いこともあり十分高速です。 よって、この問題を解くことができました。

C++ による実装例:

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define N 101
#define M 101
#define S 10001
#define INF (long long)1e+16

int main() {
	int n,m;
	int x;
	long long y;
	int a[N];
	int r[M]={};
	vector<pair<int,long long> >b;
	long long dp[M][S];

	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<m;i++){
		cin>>x>>y;
		b.push_back({x,y});
	}
	sort(b.rbegin(),b.rend());
	for(int i=0;i<m;i++){
		r[i+1]=0;
		for(int j=0;j<n;j++)r[i+1]+=min(i+1,a[j]);
	}
	
	for(int i=0;i<=m;i++)for(int j=0;j<=(n*m);j++)dp[i][j]=-INF;
	dp[0][0]=0;
	int s=0;
	rep(ii,m){
		s+=b[ii].first;
		for(int i=ii+1;i>=1;i--){
			int mx =min(s,r[i]);
			for(int j=b[ii].first;j<=mx;j++){
				dp[i][j]=max(dp[i][j],dp[i-1][j-b[ii].first]+b[ii].second);
			}
		}
	}

	long long ans=0;
	for(int i=0;i<=m;i++)for(int j=0;j<=(n*m);j++)ans=max(ans,dp[i][j]);
	cout<<ans<<endl;

	return 0;
}