#include<bits/stdc++.h> using namespace std; // #define int long long // #define LD long double // #define double long double #define it __int128 #define lson (pos<<1) #define rson (pos<<1|1) #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back #define x1 gczkaioi #define y1 lylakioi #define yjbakioi true #define popcnt __builtin_popcount #define inx(u) int I=h[u],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v int read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}x=c-'0';c=getchar();while(c<='9'&&c>='0'){x*=10;x+=c-'0';c=getchar();}return x*f;} const int MAXN=2000010,MAXM=200010,N=150,M=30,base=131,Mod=998244353,Mod2=999911659,inf=1000000000,Inf=1000000000,B=1000; int Pow(int x,int y){int rt=1;while(y){if(y&1)rt=rt*x%Mod;x=x*x%Mod,y>>=1;}return rt;} string ejz(int x){string s="";for(int i=0;i<6;i++)s+=x&(1<<i)?"1":"0";return s;} // struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT=1;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} int n,m,k,t,p[MAXN],a[MAXM],f[2][N][N]; int w[MAXN]; char c[MAXN],d[MAXN]; struct ACAM{ int t[N][M],fail[N],num[N],cnt; void clear(){ cnt=1; } void insert(int id){ int pos=1,len=strlen(d+1); for(int i=1;i<=len;i++){ if(!t[pos][w[d[i]]])t[pos][w[d[i]]]=++cnt; pos=t[pos][w[d[i]]]; } num[pos]+=a[id]; } queue<int>q; void build(){ for(int i=0;i<4;i++)t[0][i]=1; q.push(1); fail[1]=0; while(!q.empty()){ int pos=q.front();q.pop(); for(int i=0;i<4;i++){ int v=t[pos][i],F=fail[pos]; if(!v)t[pos][i]=t[F][i]; else fail[v]=t[F][i],num[v]+=num[fail[v]],q.push(v); } } } void slv(){ for(int i=1;i<=n;i++){ for(int j=1;j<=cnt;j++){ for(int k=1;k<=cnt;k++){ f[i&1][t[j][w[c[i]]]][k]=max(f[i&1][t[j][w[c[i]]]][k],f[i&1^1][j][k]+num[t[j][w[c[i]]]]); f[i&1][j][t[k][w[c[i]]]]=max(f[i&1][j][t[k][w[c[i]]]],f[i&1^1][j][k]+num[t[k][w[c[i]]]]); } } for(int j=1;j<=cnt;j++) for(int k=1;k<=cnt;k++)f[i&1^1][j][k]=-inf; } } int getans(){ int ans=0; for(int i=1;i<=cnt;i++){ memset(f,-0x3f,sizeof(f)); f[0][1][i]=0; slv(); for(int j=1;j<=cnt;j++)ans=max(ans,f[n&1][i][j]); } return ans; } }T; void slv(){ w['L']=0,w['O']=1,w['I']=2,w['J']=3; n=read(),m=read(); scanf("%s",c+1); T.clear(); for(int i=1;i<=m;i++){ p[i]=read(),a[i]=read(); scanf("%s",d+1); T.insert(i); } T.build(); printf("%lld",T.getans()); } signed main(){ // while(n=read()) slv(); return 0; }