#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<vector>
using namespace std;


int dp[60000];
int sum[10];
map<string,int> color;

int main()
{
	int M,N;
	while(~scanf("%d%d",&M,&N),M+N)
	{
		vector<int> V[10];
		for(int i=0;i<M;i++)
		{
			string c;
			cin >> c;
			color[c] = i;
		}
		memset(sum,0,sizeof sum);
		while(N--)
		{
			int v,x;
			string c;
			cin >> v >> c;
			x = color[c];
			V[x].push_back(v);
			sum[x] += v;
		}
		int ans = 0;
		for(int c=0;c<M;c++)
		{
			int s = sum[c];
			memset(dp,0,sizeof dp);
			for(int i=0;i<V[c].size();i++)
			for(int j=s;j>=V[c][i];j--)
			dp[j] = max(dp[j],dp[j-V[c][i]]+V[c][i]);
		
			for(int i=(s+1)/2;i<=s;i++)
			if(dp[i]==i)
			{
				ans += i;
			//	printf("dp[%d] = %d\n",i,dp[i]);
				break;
			}
			
		}
		printf("%d\n",ans);
		
		
	}
}