#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Max=1e3+5,inf=0x7fffffffffff;

struct trie{
public:
	struct node{
		int ch[4],add,fail;
	}p[Max];
	int tot=0;
	void add(string a,int num)
	{
		int now=0;
		for(int i=0;i<=(int)a.size()-1;i++)
		{
			if(!p[now].ch[a[i]-'0'])
				p[now].ch[a[i]-'0']=++tot;
			now=p[now].ch[a[i]-'0'];
		}
		p[now].add+=num;
	}
	queue<int> q;
	void getfail()
	{
		for(int i=0;i<=3;i++)
			if(p[0].ch[i])
				q.push(p[0].ch[i]);
		while(!q.empty())
		{
			int now=q.front();
			q.pop();
			p[now].add+=p[p[now].fail].add;
			for(int i=0;i<=3;i++)
			{
				if(p[now].ch[i])
				{
					p[p[now].ch[i]].fail=p[p[now].fail].ch[i];
					q.push(p[now].ch[i]);
				}
				else
					p[now].ch[i]=p[p[now].fail].ch[i];
			}
		}
	}
}t;
int ch[900],dp[Max][Max];
int n,m,k;
string a;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	ch['A']=0;ch['B']=1;ch['X']=2;ch['Y']=3;
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a>>k;
		for(int j=0;j<=(int)a.size()-1;j++)
		{
			a[j]=ch[(int)a[j]]+'0';
		}
		t.add(a,k);
	}
	t.getfail();
	for(int i=0;i<=m;i++)
		for(int j=0;j<=t.tot;j++)
			dp[i][j]=-inf;
	dp[0][0]=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<=t.tot;j++)
		{
			for(int k=0;k<=3;k++)
			{
				dp[i][t.p[j].ch[k]]=max(dp[i][t.p[j].ch[k]],dp[i-1][j]+t.p[t.p[j].ch[k]].add);
			}
		}
	}
	int ans=0;
	for(int i=0;i<=t.tot;i++)
		ans=max(ans,dp[m][i]);
	cout<<ans;
}