#include<bits/stdc++.h> #define uint unsigned int using namespace std; const int S=150,N=1050,SG=5; uint INF=2.8e9; 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++){ //cout<<now<<endl; 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){ for(int i=0;i<=ACAM.tot;i++)for(int j=0;j<=ACAM.tot;j++) f[op][i][j]=INF; }void cmx(uint &a,uint b){ if(a<INF&&b<INF) a=max(a,b); else a=min(a,b); } int main(){ int n,m;cin>>n>>m;string s;cin>>s; for(int i=1;i<=m;i++){ int a,b;string t; cin>>a>>b>>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;//cout<<fl<<endl; ms(fl); for(int j=0;j<=ACAM.tot;j++){ for(int k=0;k<=ACAM.tot;k++){ 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])]]); //if(f[1-fl][j][k]<INF)cout<<j<<' '<<k<<' '<<f[1-fl][j][k]<<endl; //cout<<ACAM.trie[0][1]<<endl; } }//cout<<endl; }for(int i=0;i<=ACAM.tot;i++)cmx(ans,f[fl][op][i]);//cout<<endl; }cout<<ans;//cout<<endl<<ACAMfail' '<<ACAM.trie[7][2]; return 0; }