This problem is interesting.

The first idea is to use idols with smaller \(A\) to perform songs with larger \(B\). So we sort idols in asc order of \(A\) and sort songs in dsc order of \(B\).

Then we come up with a simple dp:

\(f[o][i]=\) maximum sum of \(C\) when selecting \(i\) of the first \(o\) songs.

Consider the next song, the number of idols available \(=\sum\limits_{j=1}^n[A_j>i]\), and the song \(o+1\) can be chosen if the number \(\geq B_{o+1}\).

Imagine a histogram of \(A\) in your mind. You are doing dp on it from the bottom to the top.

However, the solution above is incorrect because some human resourses are wasted. Concretely, a row of the histogram can be longer than \(B\), and that parts are abandoned.

So we reserve these human resources and use them later.

#include<stdio.h>
#include<algorithm>
#include<string.h>
#define N 109
#define pr pair<int,int> 
using namespace std;
inline char nc()
{
	static char*l,*r,buf[99999];
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,a[N];long long ans[N][N*N],bns[N][N*N],maxn;pr b[N];
main()
{
	read(n);read(m);for(int i=0;i<n;read(a[i++]));sort(a,a+n);
	for(int i=0;i<m;++i)read(b[i].first),read(b[i].second);
	sort(b,b+m);reverse(b,b+m);
	for(int i=0;i<=m;++i)for(int j=1;j<=n*m;ans[i][j]=bns[i][j]=-(1ll<<60),++j);
	for(int i=0;i<m;++i)
	{
		for(int j=0;j<=i;++j)for(int k=0;k<=n*m;++k)
		{
			int l=upper_bound(a,a+n,j)-a;
			if(n-l+k<b[i].first)continue;
			int nxtk=n-l+k-b[i].first;
			if(nxtk>n*m)break;
			bns[j+1][nxtk]=max(bns[j+1][nxtk],ans[j][k]+b[i].second);
		}
		memcpy(ans,bns,sizeof(ans));
	}
	for(int i=0;i<=m;++i)for(int j=0;j<=n*m;++j)maxn=max(maxn,ans[i][j]);
	printf("%lld",maxn);
}