#include<bits/stdc++.h> #define uint unsigned int using namespace std; const int S=150,N=1050,SG=5; uint INF=2.8e9; inline int mp(char ch){ if(ch=='O') return 1;if(ch=='I') return 2; if(ch=='J') return 3;if(ch=='L') return 4; } struct ACAM{ int trie[S][SG],fail[S],tot=0;uint vl[S]; void ins(string s,int val){ int now=0; for(int i=0;i<s.length();i++){ int to=mp(s[i]); if(!trie[now][to]) trie[now][to]=++tot; now=trie[now][to]; }vl[now]+=val; }void bfs(){ queue<int> q; for(int i=1;i<=4;i++) if(trie[0][i]) q.push(trie[0][i]); while(!q.empty()){ int p=q.front();q.pop(); for(int i=1;i<=4;i++){ if(trie[p][i]){ fail[trie[p][i]]=trie[fail[p]][i]; q.push(trie[p][i]); }else{ trie[p][i]=trie[fail[p]][i]; } }vl[p]+=vl[fail[p]]; } } }ACAM; uint f[2][S][S]; void ms(int op){ memset(f[op],-1,sizeof(f[op])); }void cmx(uint &a,uint b){ if(a<INF&&b<INF) a=max(a,b); else a=min(a,b); }inline bool isd(char ch){ return ch>='0'&&ch<='9'; }inline bool isc(char ch){ return ch=='O'||ch=='I'||ch=='J'||ch=='L'; } int read(){ char ch=getchar();int x=0,f=1; while(!isd(ch)){ if(ch=='-') f=-1;ch=getchar(); }while(isd(ch)) x=x*10+ch-'0',ch=getchar(); return x*f; }void reads(string &s){ char ch=getchar(); while(!isc(ch)) ch=getchar(); while(isc(ch)) s+=ch,ch=getchar(); } int main(){ int n=read(),m=read();string s;reads(s); for(int i=1;i<=m;i++){ int a=read(),b=read();string t;reads(t); ACAM.ins(t,b); }uint ans=0;ACAM.bfs(); for(int op=0;op<=ACAM.tot;op++){ int fl=0;ms(0),ms(1); f[0][0][op]=0; for(int i=0;i<n;i++){ fl=1-fl; ms(fl); for(int j=0;j<=ACAM.tot;j++){ for(int k=0;k<=ACAM.tot;k++){ if(f[1-fl][j][k]==(uint)(-1)) continue; cmx(f[fl][ACAM.trie[j][mp(s[i])]][k],f[1-fl][j][k]+ACAM.vl[ACAM.trie[j][mp(s[i])]]); cmx(f[fl][j][ACAM.trie[k][mp(s[i])]],f[1-fl][j][k]+ACAM.vl[ACAM.trie[k][mp(s[i])]]); } }//cout<<endl; }for(int i=0;i<=ACAM.tot;i++)cmx(ans,f[fl][op][i]); }printf("%u",ans); return 0; }