#include<bits/stdc++.h> using namespace std; #define N 1005 #define M 22 #define uint unsigned int char s[N],t[M][M],F[200]; int n,m,i,x,j,k,l,tmp,nxt,cnt_,tmp_,nxt_,to[M*M+5][4],cnt,fail[M*M+5],val[M*M+5],f1,f2; uint dp[2][125][125][125],v[N],ans; queue<int>q; void ins(char *f){ int l=strlen(f+1),u=0,i; for(i=1;i<=l;++i){ if(!to[u][F[f[i]]])to[u][F[f[i]]]=++cnt; u=to[u][F[f[i]]]; } val[u]+=f2; } inline void Max(uint &x,uint y){if(y<x&&~x)return ;x=y;} int main(){ scanf("%d%d%s",&n,&m,s+1); F['O']=0;F['I']=1;F['L']=2;F['J']=3; for(i=1;i<=n;++i)s[i]=F[s[i]]; for(i=1;i<=m;++i)scanf("%d%d%s",&f1,&f2,t[i]+1),ins(t[i]); for(i=0;i<4;++i)if(to[0][i])q.push(to[0][i]); while(q.size()){ x=q.front();q.pop(); val[x]+=val[fail[x]]; for(i=0;i<4;++i){ if(to[x][i])fail[to[x][i]]=to[fail[x]][i],q.push(to[x][i]); else to[x][i]=to[fail[x]][i]; } } memset(dp,-1,sizeof(dp)); for(i=0;i<=cnt;++i)dp[0][0][i][i]=0; for(i=1;i<=n;++i){ nxt=tmp^1; for(j=0;j<=cnt;++j){ for(k=0;k<=cnt;++k){ f1=to[j][s[i]];f2=to[k][s[i]]; uint *g=dp[tmp][j][k],*g1=dp[nxt][f1][k],*g2=dp[nxt][j][f2]; if(~g[0]) Max(g1[0],g[0]+val[f1]), Max(g2[0],g[0]+val[f2]),g[0]=-1; if(~g[1]) Max(g1[1],g[1]+val[f1]), Max(g2[1],g[1]+val[f2]),g[1]=-1; if(~g[2]) Max(g1[2],g[2]+val[f1]), Max(g2[2],g[2]+val[f2]),g[2]=-1; if(~g[3]) Max(g1[3],g[3]+val[f1]), Max(g2[3],g[3]+val[f2]),g[3]=-1; if(~g[4]) Max(g1[4],g[4]+val[f1]), Max(g2[4],g[4]+val[f2]),g[4]=-1; if(~g[5]) Max(g1[5],g[5]+val[f1]), Max(g2[5],g[5]+val[f2]),g[5]=-1; if(~g[6]) Max(g1[6],g[6]+val[f1]), Max(g2[6],g[6]+val[f2]),g[6]=-1; if(~g[7]) Max(g1[7],g[7]+val[f1]), Max(g2[7],g[7]+val[f2]),g[7]=-1; if(~g[8]) Max(g1[8],g[8]+val[f1]), Max(g2[8],g[8]+val[f2]),g[8]=-1; if(~g[9]) Max(g1[9],g[9]+val[f1]), Max(g2[9],g[9]+val[f2]),g[9]=-1; if(~g[10]) Max(g1[10],g[10]+val[f1]), Max(g2[10],g[10]+val[f2]),g[10]=-1; if(~g[11]) Max(g1[11],g[11]+val[f1]), Max(g2[11],g[11]+val[f2]),g[11]=-1; if(~g[12]) Max(g1[12],g[12]+val[f1]), Max(g2[12],g[12]+val[f2]),g[12]=-1; if(~g[13]) Max(g1[13],g[13]+val[f1]), Max(g2[13],g[13]+val[f2]),g[13]=-1; if(~g[14]) Max(g1[14],g[14]+val[f1]), Max(g2[14],g[14]+val[f2]),g[14]=-1; if(~g[15]) Max(g1[15],g[15]+val[f1]), Max(g2[15],g[15]+val[f2]),g[15]=-1; if(~g[16]) Max(g1[16],g[16]+val[f1]), Max(g2[16],g[16]+val[f2]),g[16]=-1; if(~g[17]) Max(g1[17],g[17]+val[f1]), Max(g2[17],g[17]+val[f2]),g[17]=-1; if(~g[18]) Max(g1[18],g[18]+val[f1]), Max(g2[18],g[18]+val[f2]),g[18]=-1; if(~g[19]) Max(g1[19],g[19]+val[f1]), Max(g2[19],g[19]+val[f2]),g[19]=-1; if(~g[20]) Max(g1[20],g[20]+val[f1]), Max(g2[20],g[20]+val[f2]),g[20]=-1; if(~g[21]) Max(g1[21],g[21]+val[f1]), Max(g2[21],g[21]+val[f2]),g[21]=-1; if(~g[22]) Max(g1[22],g[22]+val[f1]), Max(g2[22],g[22]+val[f2]),g[22]=-1; if(~g[23]) Max(g1[23],g[23]+val[f1]), Max(g2[23],g[23]+val[f2]),g[23]=-1; if(~g[24]) Max(g1[24],g[24]+val[f1]), Max(g2[24],g[24]+val[f2]),g[24]=-1; if(~g[25]) Max(g1[25],g[25]+val[f1]), Max(g2[25],g[25]+val[f2]),g[25]=-1; if(~g[26]) Max(g1[26],g[26]+val[f1]), Max(g2[26],g[26]+val[f2]),g[26]=-1; if(~g[27]) Max(g1[27],g[27]+val[f1]), Max(g2[27],g[27]+val[f2]),g[27]=-1; if(~g[28]) Max(g1[28],g[28]+val[f1]), Max(g2[28],g[28]+val[f2]),g[28]=-1; if(~g[29]) Max(g1[29],g[29]+val[f1]), Max(g2[29],g[29]+val[f2]),g[29]=-1; if(~g[30]) Max(g1[30],g[30]+val[f1]), Max(g2[30],g[30]+val[f2]),g[30]=-1; if(~g[31]) Max(g1[31],g[31]+val[f1]), Max(g2[31],g[31]+val[f2]),g[31]=-1; if(~g[32]) Max(g1[32],g[32]+val[f1]), Max(g2[32],g[32]+val[f2]),g[32]=-1; if(~g[33]) Max(g1[33],g[33]+val[f1]), Max(g2[33],g[33]+val[f2]),g[33]=-1; if(~g[34]) Max(g1[34],g[34]+val[f1]), Max(g2[34],g[34]+val[f2]),g[34]=-1; if(~g[35]) Max(g1[35],g[35]+val[f1]), Max(g2[35],g[35]+val[f2]),g[35]=-1; if(~g[36]) Max(g1[36],g[36]+val[f1]), Max(g2[36],g[36]+val[f2]),g[36]=-1; if(~g[37]) Max(g1[37],g[37]+val[f1]), Max(g2[37],g[37]+val[f2]),g[37]=-1; if(~g[38]) Max(g1[38],g[38]+val[f1]), Max(g2[38],g[38]+val[f2]),g[38]=-1; if(~g[39]) Max(g1[39],g[39]+val[f1]), Max(g2[39],g[39]+val[f2]),g[39]=-1; if(~g[40]) Max(g1[40],g[40]+val[f1]), Max(g2[40],g[40]+val[f2]),g[40]=-1; if(~g[41]) Max(g1[41],g[41]+val[f1]), Max(g2[41],g[41]+val[f2]),g[41]=-1; if(~g[42]) Max(g1[42],g[42]+val[f1]), Max(g2[42],g[42]+val[f2]),g[42]=-1; if(~g[43]) Max(g1[43],g[43]+val[f1]), Max(g2[43],g[43]+val[f2]),g[43]=-1; if(~g[44]) Max(g1[44],g[44]+val[f1]), Max(g2[44],g[44]+val[f2]),g[44]=-1; if(~g[45]) Max(g1[45],g[45]+val[f1]), Max(g2[45],g[45]+val[f2]),g[45]=-1; if(~g[46]) Max(g1[46],g[46]+val[f1]), Max(g2[46],g[46]+val[f2]),g[46]=-1; if(~g[47]) Max(g1[47],g[47]+val[f1]), Max(g2[47],g[47]+val[f2]),g[47]=-1; if(~g[48]) Max(g1[48],g[48]+val[f1]), Max(g2[48],g[48]+val[f2]),g[48]=-1; if(~g[49]) Max(g1[49],g[49]+val[f1]), Max(g2[49],g[49]+val[f2]),g[49]=-1; if(~g[50]) Max(g1[50],g[50]+val[f1]), Max(g2[50],g[50]+val[f2]),g[50]=-1; if(~g[51]) Max(g1[51],g[51]+val[f1]), Max(g2[51],g[51]+val[f2]),g[51]=-1; if(~g[52]) Max(g1[52],g[52]+val[f1]), Max(g2[52],g[52]+val[f2]),g[52]=-1; if(~g[53]) Max(g1[53],g[53]+val[f1]), Max(g2[53],g[53]+val[f2]),g[53]=-1; if(~g[54]) Max(g1[54],g[54]+val[f1]), Max(g2[54],g[54]+val[f2]),g[54]=-1; if(~g[55]) Max(g1[55],g[55]+val[f1]), Max(g2[55],g[55]+val[f2]),g[55]=-1; if(~g[56]) Max(g1[56],g[56]+val[f1]), Max(g2[56],g[56]+val[f2]),g[56]=-1; if(~g[57]) Max(g1[57],g[57]+val[f1]), Max(g2[57],g[57]+val[f2]),g[57]=-1; if(~g[58]) Max(g1[58],g[58]+val[f1]), Max(g2[58],g[58]+val[f2]),g[58]=-1; if(~g[59]) Max(g1[59],g[59]+val[f1]), Max(g2[59],g[59]+val[f2]),g[59]=-1; if(~g[60]) Max(g1[60],g[60]+val[f1]), Max(g2[60],g[60]+val[f2]),g[60]=-1; if(~g[61]) Max(g1[61],g[61]+val[f1]), Max(g2[61],g[61]+val[f2]),g[61]=-1; if(~g[62]) Max(g1[62],g[62]+val[f1]), Max(g2[62],g[62]+val[f2]),g[62]=-1; if(~g[63]) Max(g1[63],g[63]+val[f1]), Max(g2[63],g[63]+val[f2]),g[63]=-1; if(~g[64]) Max(g1[64],g[64]+val[f1]), Max(g2[64],g[64]+val[f2]),g[64]=-1; if(~g[65]) Max(g1[65],g[65]+val[f1]), Max(g2[65],g[65]+val[f2]),g[65]=-1; if(~g[66]) Max(g1[66],g[66]+val[f1]), Max(g2[66],g[66]+val[f2]),g[66]=-1; if(~g[67]) Max(g1[67],g[67]+val[f1]), Max(g2[67],g[67]+val[f2]),g[67]=-1; if(~g[68]) Max(g1[68],g[68]+val[f1]), Max(g2[68],g[68]+val[f2]),g[68]=-1; if(~g[69]) Max(g1[69],g[69]+val[f1]), Max(g2[69],g[69]+val[f2]),g[69]=-1; if(~g[70]) Max(g1[70],g[70]+val[f1]), Max(g2[70],g[70]+val[f2]),g[70]=-1; if(~g[71]) Max(g1[71],g[71]+val[f1]), Max(g2[71],g[71]+val[f2]),g[71]=-1; if(~g[72]) Max(g1[72],g[72]+val[f1]), Max(g2[72],g[72]+val[f2]),g[72]=-1; if(~g[73]) Max(g1[73],g[73]+val[f1]), Max(g2[73],g[73]+val[f2]),g[73]=-1; if(~g[74]) Max(g1[74],g[74]+val[f1]), Max(g2[74],g[74]+val[f2]),g[74]=-1; if(~g[75]) Max(g1[75],g[75]+val[f1]), Max(g2[75],g[75]+val[f2]),g[75]=-1; if(~g[76]) Max(g1[76],g[76]+val[f1]), Max(g2[76],g[76]+val[f2]),g[76]=-1; if(~g[77]) Max(g1[77],g[77]+val[f1]), Max(g2[77],g[77]+val[f2]),g[77]=-1; if(~g[78]) Max(g1[78],g[78]+val[f1]), Max(g2[78],g[78]+val[f2]),g[78]=-1; if(~g[79]) Max(g1[79],g[79]+val[f1]), Max(g2[79],g[79]+val[f2]),g[79]=-1; if(~g[80]) Max(g1[80],g[80]+val[f1]), Max(g2[80],g[80]+val[f2]),g[80]=-1; if(~g[81]) Max(g1[81],g[81]+val[f1]), Max(g2[81],g[81]+val[f2]),g[81]=-1; if(~g[82]) Max(g1[82],g[82]+val[f1]), Max(g2[82],g[82]+val[f2]),g[82]=-1; if(~g[83]) Max(g1[83],g[83]+val[f1]), Max(g2[83],g[83]+val[f2]),g[83]=-1; if(~g[84]) Max(g1[84],g[84]+val[f1]), Max(g2[84],g[84]+val[f2]),g[84]=-1; if(~g[85]) Max(g1[85],g[85]+val[f1]), Max(g2[85],g[85]+val[f2]),g[85]=-1; if(~g[86]) Max(g1[86],g[86]+val[f1]), Max(g2[86],g[86]+val[f2]),g[86]=-1; if(~g[87]) Max(g1[87],g[87]+val[f1]), Max(g2[87],g[87]+val[f2]),g[87]=-1; if(~g[88]) Max(g1[88],g[88]+val[f1]), Max(g2[88],g[88]+val[f2]),g[88]=-1; if(~g[89]) Max(g1[89],g[89]+val[f1]), Max(g2[89],g[89]+val[f2]),g[89]=-1; if(~g[90]) Max(g1[90],g[90]+val[f1]), Max(g2[90],g[90]+val[f2]),g[90]=-1; if(~g[91]) Max(g1[91],g[91]+val[f1]), Max(g2[91],g[91]+val[f2]),g[91]=-1; if(~g[92]) Max(g1[92],g[92]+val[f1]), Max(g2[92],g[92]+val[f2]),g[92]=-1; if(~g[93]) Max(g1[93],g[93]+val[f1]), Max(g2[93],g[93]+val[f2]),g[93]=-1; if(~g[94]) Max(g1[94],g[94]+val[f1]), Max(g2[94],g[94]+val[f2]),g[94]=-1; if(~g[95]) Max(g1[95],g[95]+val[f1]), Max(g2[95],g[95]+val[f2]),g[95]=-1; if(~g[96]) Max(g1[96],g[96]+val[f1]), Max(g2[96],g[96]+val[f2]),g[96]=-1; if(~g[97]) Max(g1[97],g[97]+val[f1]), Max(g2[97],g[97]+val[f2]),g[97]=-1; if(~g[98]) Max(g1[98],g[98]+val[f1]), Max(g2[98],g[98]+val[f2]),g[98]=-1; if(~g[99]) Max(g1[99],g[99]+val[f1]), Max(g2[99],g[99]+val[f2]),g[99]=-1; if(~g[100]) Max(g1[100],g[100]+val[f1]), Max(g2[100],g[100]+val[f2]),g[100]=-1; if(~g[101]) Max(g1[101],g[101]+val[f1]), Max(g2[101],g[101]+val[f2]),g[101]=-1; if(~g[102]) Max(g1[102],g[102]+val[f1]), Max(g2[102],g[102]+val[f2]),g[102]=-1; if(~g[103]) Max(g1[103],g[103]+val[f1]), Max(g2[103],g[103]+val[f2]),g[103]=-1; if(~g[104]) Max(g1[104],g[104]+val[f1]), Max(g2[104],g[104]+val[f2]),g[104]=-1; if(~g[105]) Max(g1[105],g[105]+val[f1]), Max(g2[105],g[105]+val[f2]),g[105]=-1; if(~g[106]) Max(g1[106],g[106]+val[f1]), Max(g2[106],g[106]+val[f2]),g[106]=-1; if(~g[107]) Max(g1[107],g[107]+val[f1]), Max(g2[107],g[107]+val[f2]),g[107]=-1; if(~g[108]) Max(g1[108],g[108]+val[f1]), Max(g2[108],g[108]+val[f2]),g[108]=-1; if(~g[109]) Max(g1[109],g[109]+val[f1]), Max(g2[109],g[109]+val[f2]),g[109]=-1; if(~g[110]) Max(g1[110],g[110]+val[f1]), Max(g2[110],g[110]+val[f2]),g[110]=-1; if(~g[111]) Max(g1[111],g[111]+val[f1]), Max(g2[111],g[111]+val[f2]),g[111]=-1; if(~g[112]) Max(g1[112],g[112]+val[f1]), Max(g2[112],g[112]+val[f2]),g[112]=-1; if(~g[113]) Max(g1[113],g[113]+val[f1]), Max(g2[113],g[113]+val[f2]),g[113]=-1; if(~g[114]) Max(g1[114],g[114]+val[f1]), Max(g2[114],g[114]+val[f2]),g[114]=-1; if(~g[115]) Max(g1[115],g[115]+val[f1]), Max(g2[115],g[115]+val[f2]),g[115]=-1; if(~g[116]) Max(g1[116],g[116]+val[f1]), Max(g2[116],g[116]+val[f2]),g[116]=-1; if(~g[117]) Max(g1[117],g[117]+val[f1]), Max(g2[117],g[117]+val[f2]),g[117]=-1; if(~g[118]) Max(g1[118],g[118]+val[f1]), Max(g2[118],g[118]+val[f2]),g[118]=-1; if(~g[119]) Max(g1[119],g[119]+val[f1]), Max(g2[119],g[119]+val[f2]),g[119]=-1; if(~g[120]) Max(g1[120],g[120]+val[f1]), Max(g2[120],g[120]+val[f2]),g[120]=-1; } } tmp^=1; } for(i=0;i<=cnt;++i)for(j=0;j<=cnt;++j)if(~dp[tmp][i][j][i])Max(ans,dp[tmp][i][j][i]); cout<<ans; }