// POJ 3211
#include <map>
#include <vector>
#include <string>
#include <iostream>
using namespace std;

const int MAXN3211 = 100002;
const int MAXM3211 = 11;

map<string, int> colors3211;

vector<int> clothes3211[MAXM3211];
int ans3211[MAXN3211];

int main(void)
{
	int i, j, k, m, n, num, sum, mid, ans;
	string color;

	while((cin >> m >> n) && (m || n))
	{
		for(i = 1; i <= m; ++i)
		{
			cin >> color;
			colors3211[color] = i;
			clothes3211[i].clear();	
		}
		for(i = 0; i < n; ++i)
		{
			cin >> num >> color;
			clothes3211[colors3211[color]].push_back(num);
		}
		memset(ans3211, 0, sizeof(ans3211));
		ans = 0;
		for(i = 1; i <= m; ++i)
		{
			for(sum = j = 0; j < clothes3211[i].size(); ++j)
				sum += clothes3211[i][j];	// 第i种颜色的衣服的总时长
			mid = sum >> 1;		// 平均点，使第一个人洗的时间尽量靠近该时间
			// 以平均点为容量求解01背包，算出第一个的最大时间(<=mid)
			for(j = 0; j < clothes3211[i].size(); ++j)
			{
				for(k = mid; k >= clothes3211[i][j]; --k)
					if(ans3211[k - clothes3211[i][j]] + clothes3211[i][j] > ans3211[k])
						ans3211[k] = ans3211[k - clothes3211[i][j]] + clothes3211[i][j];
			}
			ans += sum - ans3211[mid];	// 最长时间，即第二个人完成的时间
		}
		cout << ans << endl;
	}
	return 0;
}

/*
Sample Input

3 4
red blue yellow
2 red
3 blue
4 blue
6 red

3 4
red blue yellow
3 red
3 red
4 blue
4 blue 

2 8
red blue
4 red
7 red
5 red
5 blue
4 red
7 blue
4 red
3 blue

0 0
Sample Output

10
7
20
*/