#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
const int mod=998244353;
struct mint{
    int x;mint(int o=0){x=o;}mint&operator+=(mint a){return(x+=a.x)%=mod,*this;}mint&operator-=(mint a){return(x+=mod-a.x)%=mod,*this;}
    mint&operator*=(mint a){return(x=1ll*x*a.x%mod),*this;}mint&operator^=( int b){mint a=*this;x=1;while(b)(b&1)&&(*this*=a,1),a*=a,b>>=1;return*this;}
    mint&operator/=(mint a){return*this*=(a^=mod-2);}friend mint operator+(mint a,mint b){return a+=b;}friend mint operator-(mint a,mint b){return a-=b;}
    friend mint operator*(mint a,mint b){return a*=b;}friend mint operator/(mint a,mint b){return a/=b;}friend mint operator^(mint a,int b){return a^=b;}
    mint operator-(){return 0-*this;}bool operator==(const mint b)const{return x==b.x;}
};
int m,n;
char s[1005][1005];
int d[1005];
int res;
char p[1005];
void dfs(int x){
	if(x==m+1){
		int cnt=0;
		for(int i=1;i<=n;i++){
			int len=strlen(s[i]+1);
			for(int j=1;j+len-1<=m;j++){
				bool ok=1;
				for(int k=j;k<j+len;k++)ok&=(p[k]==s[i][k-j+1]);
				if(ok){cnt+=d[i];}
			}
		}
		res=max(res,cnt);
		return;
	}
	p[x]='A';dfs(x+1);
	p[x]='B';dfs(x+1);
	p[x]='X';dfs(x+1);
	p[x]='Y';dfs(x+1);
}
void work(){
	dfs(1);
	printf("%lld\n",res);
}
signed main(){
	m=read(),n=read();
	for(int i=1;i<=n;i++){
		scanf("%s",s[i]+1);
		d[i]=read();
	}
	if(n<=10&&m<=10){work();return 0;}
	return 0;
}