#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1005; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,m; string S; struct AC { struct nd { int son[4],fail,c; }d[155]; ll dp[2][155][155];int ct; void ins(string &s,int v){ int u=0; for(char ch:s){ int o=ch-'a'; if(!d[u].son[o])d[u].son[o]=++ct; u=d[u].son[o]; }d[u].c+=v; }void bd(){ queue<int>q; up(i,0,3)if(d[0].son[i])q.push(d[0].son[i]); while(!q.empty()){ int u=q.front();q.pop(); d[u].c+=d[d[u].fail].c; up(i,0,3){ if(d[u].son[i])d[d[u].son[i]].fail=d[d[u].fail].son[i],q.push(d[u].son[i]); else d[u].son[i]=d[d[u].fail].son[i]; } } }ll calc_dp(){ ll res=0; up(i,0,ct){ memset(dp,128,sizeof(dp)); dp[0][0][i]=0; up(j,0,n-1){ int op=j&1; memset(dp[!op],128,sizeof(dp[!op])); up(k,0,ct){ up(l,0,ct){ if(dp[op][k][l]<0)continue; int x=d[l].son[S[j]-'a']; dp[!op][k][x]=max(dp[!op][k][x],dp[op][k][l]+d[x].c); x=d[k].son[S[j]-'a']; dp[!op][x][l]=max(dp[!op][x][l],dp[op][k][l]+d[x].c); } } }int op=n&1;up(j,0,ct)res=max(res,dp[op][i][j]); }return res; } }T; char g(char ch){ if(ch=='O')return 'a'; if(ch=='I')return 'b'; if(ch=='L')return 'c'; return 'd'; } void slv(){ cin>>n>>m; cin>>S;for(char &ch:S)ch=g(ch); up(i,1,m){ int len=0,val=0;string t; cin>>len>>val>>t;for(char &ch:t)ch=g(ch); T.ins(t,val); }T.bd(); cout<<T.calc_dp(); }int main(){ //freopen("tetr.in","r",stdin); //freopen("tetr.out","w",stdout); slv(); fclose(stdin); fclose(stdout); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }