#include <bits/stdc++.h> using namespace std; #define ui unsigned int int n,m; string s; ui f[2][131][131][131]; int c[131][4],w[131],fa[131]; int cnt=0; map<char,int>id; inline void chkmx(ui &x,ui y){if((~x)&&x>=y)return ;x=y;} signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // int C=clock(); // freopen("genshin.in","r",stdin); // freopen("genshin.out","w",stdout); cin>>n>>m>>s; id['O']=0,id['L']=1,id['J']=2,id['I']=3; for(int i=1;i<=m;i++){ int l,cs; cin>>l>>cs; string t; cin>>t; int now=0; for(char x:t){ x=id[x]; if(!c[now][x])c[now][x]=++cnt; now=c[now][x]; } w[now]+=cs; } queue<int>q; for(int i=0;i<4;i++) if(c[0][i])q.push(c[0][i]); while(!q.empty()){ int u=q.front(); q.pop(); w[u]+=w[fa[u]]; for(int i=0;i<4;i++) if(c[u][i])fa[c[u][i]]=c[fa[u]][i],q.push(c[u][i]); else c[u][i]=c[fa[u]][i]; } ui res=-1; bool fl=0; memset(f,0xff,sizeof(f)); for(int p=0;p<=cnt;p++) f[fl][0][p][p]=0; for(char x:s){ fl^=1; x=id[x]; memset(f[fl],0xff,sizeof(f[fl])); for(int i=0;i<=cnt;i++) for(int j=0;j<=cnt;j++){ ui fi=c[i][x],fj=c[j][x]; ui wi=w[c[i][x]],wj=w[c[j][x]]; ui *g=f[!fl][i][j]; ui *gi=f[fl][fi][j],*gj=f[fl][i][fj]; for(int k=0;k<=cnt;k++) if(~g[k]) chkmx(gi[k],g[k]+wi),chkmx(gj[k],g[k]+wj); } } for(int i=0;i<=cnt;i++) for(int j=0;j<=cnt;j++) if(~f[fl][i][j][i]) chkmx(res,f[fl][i][j][i]); cout<<res<<endl; // cerr<<(clock()-C)*1000/CLOCKS_PER_SEC<<endl; cout.flush(); return 0; }