#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m;
char colour[11][13];
int ti[11][110],rep[11];
bool flag[1000010];
int main()
{
	int i,j,t,z,sum;
	char now[13];
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(!(m|n))break;
		memset(ti,0,sizeof(ti));
		memset(rep,0,sizeof(rep));
		memset(colour,0,sizeof(colour));
		sum=0;
		for(i=0;i<n;i++)
		   scanf("%s",colour[i]);
		for(i=0;i<m;i++)
		{
			cin>>t;
		    scanf("%s",now);
			for(j=0;j<n;j++)
				if(!strcmp(now,colour[j]))
					break;
			ti[j][rep[j]]=t;
				rep[j]++;
		}
		for(i=0;i<n;i++)
		{
			memset(flag,false,sizeof(flag));
			flag[0]=true;
			int cnt=0;
			for(j=0;j<rep[i];j++)
			{
				for(z=0;z<=cnt;z++)
				{
					if(flag[z])
						flag[z+ti[i][j]]=true;
				}
				cnt+=ti[i][j];
			}
			int small=1000010,qq,yy=0;
			for(j=0;j<=cnt;j++)
			{
				if(flag[j])
				{
					qq=abs(cnt-2*j);
					if(qq<=small)
					{
						small=qq;
						yy=j;
					}
					else break;
				}
			}
			if(yy<cnt-yy)yy=cnt-yy;
			sum+=yy;
		}
		printf("%d\n",sum);
	}
	return 0;
}