#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector <int> v[15];
int sum[15];
int dp[1000005];
struct Clo
{
    int t;
    char c[15];       
}clo[105];
char col[15][15];
int main()
{
    int n,m;
    while(1)
    {
        scanf("%d%d",&m,&n);
        if(m==0&&n==0)break;
        for(int i=0;i<m;i++)scanf("%s",&col[i]);
        for(int i=0;i<n;i++)scanf("%d %s",&clo[i].t,&clo[i].c);
        for(int i=0;i<=m;i++)v[i].clear(),sum[i]=0;
        for(int i=0;i<n;i++)
           for(int j=0;j<m;j++)
              if(strcmp(col[j],clo[i].c)==0)v[j].push_back(clo[i].t);
        for(int i=0;i<m;i++)
           for(int j=0;j<v[i].size();j++)sum[i]+=v[i][j];
        int ans=0;
        for(int i=0;i<m;i++)
        {
           for(int j=0;j<=sum[i]/2;j++)dp[i]=0;
           for(int j=0;j<v[i].size();j++)
              for(int k=sum[i]/2;k>=v[i][j];k--)
                 dp[k]=max(dp[k],dp[k-v[i][j]]+v[i][j]);
           ans+=(sum[i]-dp[sum[i]/2]);
        }
        printf("%d\n",ans);
    }
    return 0;
}