#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1 << 28)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 200111

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

int h, t;
int arr[maxn];
vector<pair<int, int>> robbers;
map<vector<int>, int> dp[20];

int f(int i, vector<int> v){
	if(v.size() == 0){
		return 0;
	}

	if(i == t){
		return -INF;
	}

	if(dp[i].count(v)){
		return dp[i][v];
	}

	int val = f(i + 1, v);
	for(int j = 0; j < v.size(); j++){
		if(v[j] >= robbers[i].fi){
			vector<int> v_new = v;
			v_new[j] -= robbers[i].fi;
			if(v_new[j] == 0){
				v_new.erase(v_new.begin() + j);
			}

			sort(v_new.begin(), v_new.end());
			val = max(val, robbers[i].se + f(i + 1, v_new));
		}		
	}

	dp[i][v] = val;
	return val;
}

int main(){
	vector<int> v;
	scanf("%d%d", &h, &t);
	for(int i = 0; i < h; i++){
		int k;
		scanf("%d", &k);
		if(k > t){
			printf("0");
			return 0;
		}

		for(int i = t + 1; i < 100; i++){
			if(arr[i] > 0){
				v.pb(arr[i]);
				arr[i] = 0;
			}
		}

		for(int i = 1; i <= k; i++){
			arr[i]++;
		}
	}

	for(int i = 1; i < 100; i++){
		if(arr[i] > 0){
			v.pb(arr[i]);
		}
	}	
	sort(v.begin(), v.end());

	for(int x : v){
		printf("%d ", x);
	}




	int sum_robbers = 0;
	for(int i = 0; i < t; i++){
		int d, c;
		scanf("%d%d", &d, &c);
		robbers.pb(mp(d, c));
		sum_robbers += d;
	}

	int sum_clear = 0;
	for(int x : v){
		sum_clear += x;
	}

	if(v.size() > t || sum_clear > sum_robbers){
		printf("0");
		return 0;
	}

	printf("%d", f(0, v));

	return 0;
}