#include<bits/stdc++.h> using namespace std; // #define int long long // #define LD long double // #define double long double #define unt unsigned int #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=130,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]; unsigned int f[2][N][N][N]; int w[MAXN]; char c[MAXN],d[MAXN]; unt Max(unt x,unt y){return ~x?~y?x>y?x:y:x:y;} 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++){ if(~f[i&1^1][j][k][1])f[i&1][t[j][w[c[i]]]][k][1]=Max(f[i&1][t[j][w[c[i]]]][k][1],f[i&1^1][j][k][1]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][1]=Max(f[i&1][j][t[k][w[c[i]]]][1],f[i&1^1][j][k][1]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][1]=-1; if(~f[i&1^1][j][k][2])f[i&1][t[j][w[c[i]]]][k][2]=Max(f[i&1][t[j][w[c[i]]]][k][2],f[i&1^1][j][k][2]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][2]=Max(f[i&1][j][t[k][w[c[i]]]][2],f[i&1^1][j][k][2]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][2]=-1; if(~f[i&1^1][j][k][3])f[i&1][t[j][w[c[i]]]][k][3]=Max(f[i&1][t[j][w[c[i]]]][k][3],f[i&1^1][j][k][3]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][3]=Max(f[i&1][j][t[k][w[c[i]]]][3],f[i&1^1][j][k][3]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][3]=-1; if(~f[i&1^1][j][k][4])f[i&1][t[j][w[c[i]]]][k][4]=Max(f[i&1][t[j][w[c[i]]]][k][4],f[i&1^1][j][k][4]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][4]=Max(f[i&1][j][t[k][w[c[i]]]][4],f[i&1^1][j][k][4]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][4]=-1; if(~f[i&1^1][j][k][5])f[i&1][t[j][w[c[i]]]][k][5]=Max(f[i&1][t[j][w[c[i]]]][k][5],f[i&1^1][j][k][5]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][5]=Max(f[i&1][j][t[k][w[c[i]]]][5],f[i&1^1][j][k][5]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][5]=-1; if(~f[i&1^1][j][k][6])f[i&1][t[j][w[c[i]]]][k][6]=Max(f[i&1][t[j][w[c[i]]]][k][6],f[i&1^1][j][k][6]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][6]=Max(f[i&1][j][t[k][w[c[i]]]][6],f[i&1^1][j][k][6]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][6]=-1; if(~f[i&1^1][j][k][7])f[i&1][t[j][w[c[i]]]][k][7]=Max(f[i&1][t[j][w[c[i]]]][k][7],f[i&1^1][j][k][7]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][7]=Max(f[i&1][j][t[k][w[c[i]]]][7],f[i&1^1][j][k][7]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][7]=-1; if(~f[i&1^1][j][k][8])f[i&1][t[j][w[c[i]]]][k][8]=Max(f[i&1][t[j][w[c[i]]]][k][8],f[i&1^1][j][k][8]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][8]=Max(f[i&1][j][t[k][w[c[i]]]][8],f[i&1^1][j][k][8]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][8]=-1; if(~f[i&1^1][j][k][9])f[i&1][t[j][w[c[i]]]][k][9]=Max(f[i&1][t[j][w[c[i]]]][k][9],f[i&1^1][j][k][9]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][9]=Max(f[i&1][j][t[k][w[c[i]]]][9],f[i&1^1][j][k][9]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][9]=-1; if(~f[i&1^1][j][k][10])f[i&1][t[j][w[c[i]]]][k][10]=Max(f[i&1][t[j][w[c[i]]]][k][10],f[i&1^1][j][k][10]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][10]=Max(f[i&1][j][t[k][w[c[i]]]][10],f[i&1^1][j][k][10]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][10]=-1; if(~f[i&1^1][j][k][11])f[i&1][t[j][w[c[i]]]][k][11]=Max(f[i&1][t[j][w[c[i]]]][k][11],f[i&1^1][j][k][11]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][11]=Max(f[i&1][j][t[k][w[c[i]]]][11],f[i&1^1][j][k][11]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][11]=-1; if(~f[i&1^1][j][k][12])f[i&1][t[j][w[c[i]]]][k][12]=Max(f[i&1][t[j][w[c[i]]]][k][12],f[i&1^1][j][k][12]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][12]=Max(f[i&1][j][t[k][w[c[i]]]][12],f[i&1^1][j][k][12]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][12]=-1; if(~f[i&1^1][j][k][13])f[i&1][t[j][w[c[i]]]][k][13]=Max(f[i&1][t[j][w[c[i]]]][k][13],f[i&1^1][j][k][13]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][13]=Max(f[i&1][j][t[k][w[c[i]]]][13],f[i&1^1][j][k][13]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][13]=-1; if(~f[i&1^1][j][k][14])f[i&1][t[j][w[c[i]]]][k][14]=Max(f[i&1][t[j][w[c[i]]]][k][14],f[i&1^1][j][k][14]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][14]=Max(f[i&1][j][t[k][w[c[i]]]][14],f[i&1^1][j][k][14]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][14]=-1; if(~f[i&1^1][j][k][15])f[i&1][t[j][w[c[i]]]][k][15]=Max(f[i&1][t[j][w[c[i]]]][k][15],f[i&1^1][j][k][15]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][15]=Max(f[i&1][j][t[k][w[c[i]]]][15],f[i&1^1][j][k][15]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][15]=-1; if(~f[i&1^1][j][k][16])f[i&1][t[j][w[c[i]]]][k][16]=Max(f[i&1][t[j][w[c[i]]]][k][16],f[i&1^1][j][k][16]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][16]=Max(f[i&1][j][t[k][w[c[i]]]][16],f[i&1^1][j][k][16]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][16]=-1; if(~f[i&1^1][j][k][17])f[i&1][t[j][w[c[i]]]][k][17]=Max(f[i&1][t[j][w[c[i]]]][k][17],f[i&1^1][j][k][17]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][17]=Max(f[i&1][j][t[k][w[c[i]]]][17],f[i&1^1][j][k][17]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][17]=-1; if(~f[i&1^1][j][k][18])f[i&1][t[j][w[c[i]]]][k][18]=Max(f[i&1][t[j][w[c[i]]]][k][18],f[i&1^1][j][k][18]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][18]=Max(f[i&1][j][t[k][w[c[i]]]][18],f[i&1^1][j][k][18]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][18]=-1; if(~f[i&1^1][j][k][19])f[i&1][t[j][w[c[i]]]][k][19]=Max(f[i&1][t[j][w[c[i]]]][k][19],f[i&1^1][j][k][19]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][19]=Max(f[i&1][j][t[k][w[c[i]]]][19],f[i&1^1][j][k][19]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][19]=-1; if(~f[i&1^1][j][k][20])f[i&1][t[j][w[c[i]]]][k][20]=Max(f[i&1][t[j][w[c[i]]]][k][20],f[i&1^1][j][k][20]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][20]=Max(f[i&1][j][t[k][w[c[i]]]][20],f[i&1^1][j][k][20]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][20]=-1; if(~f[i&1^1][j][k][21])f[i&1][t[j][w[c[i]]]][k][21]=Max(f[i&1][t[j][w[c[i]]]][k][21],f[i&1^1][j][k][21]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][21]=Max(f[i&1][j][t[k][w[c[i]]]][21],f[i&1^1][j][k][21]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][21]=-1; if(~f[i&1^1][j][k][22])f[i&1][t[j][w[c[i]]]][k][22]=Max(f[i&1][t[j][w[c[i]]]][k][22],f[i&1^1][j][k][22]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][22]=Max(f[i&1][j][t[k][w[c[i]]]][22],f[i&1^1][j][k][22]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][22]=-1; if(~f[i&1^1][j][k][23])f[i&1][t[j][w[c[i]]]][k][23]=Max(f[i&1][t[j][w[c[i]]]][k][23],f[i&1^1][j][k][23]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][23]=Max(f[i&1][j][t[k][w[c[i]]]][23],f[i&1^1][j][k][23]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][23]=-1; if(~f[i&1^1][j][k][24])f[i&1][t[j][w[c[i]]]][k][24]=Max(f[i&1][t[j][w[c[i]]]][k][24],f[i&1^1][j][k][24]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][24]=Max(f[i&1][j][t[k][w[c[i]]]][24],f[i&1^1][j][k][24]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][24]=-1; if(~f[i&1^1][j][k][25])f[i&1][t[j][w[c[i]]]][k][25]=Max(f[i&1][t[j][w[c[i]]]][k][25],f[i&1^1][j][k][25]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][25]=Max(f[i&1][j][t[k][w[c[i]]]][25],f[i&1^1][j][k][25]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][25]=-1; if(~f[i&1^1][j][k][26])f[i&1][t[j][w[c[i]]]][k][26]=Max(f[i&1][t[j][w[c[i]]]][k][26],f[i&1^1][j][k][26]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][26]=Max(f[i&1][j][t[k][w[c[i]]]][26],f[i&1^1][j][k][26]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][26]=-1; if(~f[i&1^1][j][k][27])f[i&1][t[j][w[c[i]]]][k][27]=Max(f[i&1][t[j][w[c[i]]]][k][27],f[i&1^1][j][k][27]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][27]=Max(f[i&1][j][t[k][w[c[i]]]][27],f[i&1^1][j][k][27]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][27]=-1; if(~f[i&1^1][j][k][28])f[i&1][t[j][w[c[i]]]][k][28]=Max(f[i&1][t[j][w[c[i]]]][k][28],f[i&1^1][j][k][28]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][28]=Max(f[i&1][j][t[k][w[c[i]]]][28],f[i&1^1][j][k][28]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][28]=-1; if(~f[i&1^1][j][k][29])f[i&1][t[j][w[c[i]]]][k][29]=Max(f[i&1][t[j][w[c[i]]]][k][29],f[i&1^1][j][k][29]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][29]=Max(f[i&1][j][t[k][w[c[i]]]][29],f[i&1^1][j][k][29]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][29]=-1; if(~f[i&1^1][j][k][30])f[i&1][t[j][w[c[i]]]][k][30]=Max(f[i&1][t[j][w[c[i]]]][k][30],f[i&1^1][j][k][30]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][30]=Max(f[i&1][j][t[k][w[c[i]]]][30],f[i&1^1][j][k][30]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][30]=-1; if(~f[i&1^1][j][k][31])f[i&1][t[j][w[c[i]]]][k][31]=Max(f[i&1][t[j][w[c[i]]]][k][31],f[i&1^1][j][k][31]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][31]=Max(f[i&1][j][t[k][w[c[i]]]][31],f[i&1^1][j][k][31]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][31]=-1; if(~f[i&1^1][j][k][32])f[i&1][t[j][w[c[i]]]][k][32]=Max(f[i&1][t[j][w[c[i]]]][k][32],f[i&1^1][j][k][32]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][32]=Max(f[i&1][j][t[k][w[c[i]]]][32],f[i&1^1][j][k][32]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][32]=-1; if(~f[i&1^1][j][k][33])f[i&1][t[j][w[c[i]]]][k][33]=Max(f[i&1][t[j][w[c[i]]]][k][33],f[i&1^1][j][k][33]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][33]=Max(f[i&1][j][t[k][w[c[i]]]][33],f[i&1^1][j][k][33]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][33]=-1; if(~f[i&1^1][j][k][34])f[i&1][t[j][w[c[i]]]][k][34]=Max(f[i&1][t[j][w[c[i]]]][k][34],f[i&1^1][j][k][34]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][34]=Max(f[i&1][j][t[k][w[c[i]]]][34],f[i&1^1][j][k][34]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][34]=-1; if(~f[i&1^1][j][k][35])f[i&1][t[j][w[c[i]]]][k][35]=Max(f[i&1][t[j][w[c[i]]]][k][35],f[i&1^1][j][k][35]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][35]=Max(f[i&1][j][t[k][w[c[i]]]][35],f[i&1^1][j][k][35]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][35]=-1; if(~f[i&1^1][j][k][36])f[i&1][t[j][w[c[i]]]][k][36]=Max(f[i&1][t[j][w[c[i]]]][k][36],f[i&1^1][j][k][36]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][36]=Max(f[i&1][j][t[k][w[c[i]]]][36],f[i&1^1][j][k][36]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][36]=-1; if(~f[i&1^1][j][k][37])f[i&1][t[j][w[c[i]]]][k][37]=Max(f[i&1][t[j][w[c[i]]]][k][37],f[i&1^1][j][k][37]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][37]=Max(f[i&1][j][t[k][w[c[i]]]][37],f[i&1^1][j][k][37]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][37]=-1; if(~f[i&1^1][j][k][38])f[i&1][t[j][w[c[i]]]][k][38]=Max(f[i&1][t[j][w[c[i]]]][k][38],f[i&1^1][j][k][38]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][38]=Max(f[i&1][j][t[k][w[c[i]]]][38],f[i&1^1][j][k][38]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][38]=-1; if(~f[i&1^1][j][k][39])f[i&1][t[j][w[c[i]]]][k][39]=Max(f[i&1][t[j][w[c[i]]]][k][39],f[i&1^1][j][k][39]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][39]=Max(f[i&1][j][t[k][w[c[i]]]][39],f[i&1^1][j][k][39]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][39]=-1; if(~f[i&1^1][j][k][40])f[i&1][t[j][w[c[i]]]][k][40]=Max(f[i&1][t[j][w[c[i]]]][k][40],f[i&1^1][j][k][40]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][40]=Max(f[i&1][j][t[k][w[c[i]]]][40],f[i&1^1][j][k][40]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][40]=-1; if(~f[i&1^1][j][k][41])f[i&1][t[j][w[c[i]]]][k][41]=Max(f[i&1][t[j][w[c[i]]]][k][41],f[i&1^1][j][k][41]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][41]=Max(f[i&1][j][t[k][w[c[i]]]][41],f[i&1^1][j][k][41]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][41]=-1; if(~f[i&1^1][j][k][42])f[i&1][t[j][w[c[i]]]][k][42]=Max(f[i&1][t[j][w[c[i]]]][k][42],f[i&1^1][j][k][42]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][42]=Max(f[i&1][j][t[k][w[c[i]]]][42],f[i&1^1][j][k][42]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][42]=-1; if(~f[i&1^1][j][k][43])f[i&1][t[j][w[c[i]]]][k][43]=Max(f[i&1][t[j][w[c[i]]]][k][43],f[i&1^1][j][k][43]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][43]=Max(f[i&1][j][t[k][w[c[i]]]][43],f[i&1^1][j][k][43]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][43]=-1; if(~f[i&1^1][j][k][44])f[i&1][t[j][w[c[i]]]][k][44]=Max(f[i&1][t[j][w[c[i]]]][k][44],f[i&1^1][j][k][44]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][44]=Max(f[i&1][j][t[k][w[c[i]]]][44],f[i&1^1][j][k][44]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][44]=-1; if(~f[i&1^1][j][k][45])f[i&1][t[j][w[c[i]]]][k][45]=Max(f[i&1][t[j][w[c[i]]]][k][45],f[i&1^1][j][k][45]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][45]=Max(f[i&1][j][t[k][w[c[i]]]][45],f[i&1^1][j][k][45]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][45]=-1; if(~f[i&1^1][j][k][46])f[i&1][t[j][w[c[i]]]][k][46]=Max(f[i&1][t[j][w[c[i]]]][k][46],f[i&1^1][j][k][46]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][46]=Max(f[i&1][j][t[k][w[c[i]]]][46],f[i&1^1][j][k][46]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][46]=-1; if(~f[i&1^1][j][k][47])f[i&1][t[j][w[c[i]]]][k][47]=Max(f[i&1][t[j][w[c[i]]]][k][47],f[i&1^1][j][k][47]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][47]=Max(f[i&1][j][t[k][w[c[i]]]][47],f[i&1^1][j][k][47]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][47]=-1; if(~f[i&1^1][j][k][48])f[i&1][t[j][w[c[i]]]][k][48]=Max(f[i&1][t[j][w[c[i]]]][k][48],f[i&1^1][j][k][48]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][48]=Max(f[i&1][j][t[k][w[c[i]]]][48],f[i&1^1][j][k][48]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][48]=-1; if(~f[i&1^1][j][k][49])f[i&1][t[j][w[c[i]]]][k][49]=Max(f[i&1][t[j][w[c[i]]]][k][49],f[i&1^1][j][k][49]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][49]=Max(f[i&1][j][t[k][w[c[i]]]][49],f[i&1^1][j][k][49]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][49]=-1; if(~f[i&1^1][j][k][50])f[i&1][t[j][w[c[i]]]][k][50]=Max(f[i&1][t[j][w[c[i]]]][k][50],f[i&1^1][j][k][50]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][50]=Max(f[i&1][j][t[k][w[c[i]]]][50],f[i&1^1][j][k][50]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][50]=-1; if(~f[i&1^1][j][k][51])f[i&1][t[j][w[c[i]]]][k][51]=Max(f[i&1][t[j][w[c[i]]]][k][51],f[i&1^1][j][k][51]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][51]=Max(f[i&1][j][t[k][w[c[i]]]][51],f[i&1^1][j][k][51]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][51]=-1; if(~f[i&1^1][j][k][52])f[i&1][t[j][w[c[i]]]][k][52]=Max(f[i&1][t[j][w[c[i]]]][k][52],f[i&1^1][j][k][52]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][52]=Max(f[i&1][j][t[k][w[c[i]]]][52],f[i&1^1][j][k][52]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][52]=-1; if(~f[i&1^1][j][k][53])f[i&1][t[j][w[c[i]]]][k][53]=Max(f[i&1][t[j][w[c[i]]]][k][53],f[i&1^1][j][k][53]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][53]=Max(f[i&1][j][t[k][w[c[i]]]][53],f[i&1^1][j][k][53]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][53]=-1; if(~f[i&1^1][j][k][54])f[i&1][t[j][w[c[i]]]][k][54]=Max(f[i&1][t[j][w[c[i]]]][k][54],f[i&1^1][j][k][54]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][54]=Max(f[i&1][j][t[k][w[c[i]]]][54],f[i&1^1][j][k][54]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][54]=-1; if(~f[i&1^1][j][k][55])f[i&1][t[j][w[c[i]]]][k][55]=Max(f[i&1][t[j][w[c[i]]]][k][55],f[i&1^1][j][k][55]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][55]=Max(f[i&1][j][t[k][w[c[i]]]][55],f[i&1^1][j][k][55]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][55]=-1; if(~f[i&1^1][j][k][56])f[i&1][t[j][w[c[i]]]][k][56]=Max(f[i&1][t[j][w[c[i]]]][k][56],f[i&1^1][j][k][56]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][56]=Max(f[i&1][j][t[k][w[c[i]]]][56],f[i&1^1][j][k][56]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][56]=-1; if(~f[i&1^1][j][k][57])f[i&1][t[j][w[c[i]]]][k][57]=Max(f[i&1][t[j][w[c[i]]]][k][57],f[i&1^1][j][k][57]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][57]=Max(f[i&1][j][t[k][w[c[i]]]][57],f[i&1^1][j][k][57]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][57]=-1; if(~f[i&1^1][j][k][58])f[i&1][t[j][w[c[i]]]][k][58]=Max(f[i&1][t[j][w[c[i]]]][k][58],f[i&1^1][j][k][58]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][58]=Max(f[i&1][j][t[k][w[c[i]]]][58],f[i&1^1][j][k][58]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][58]=-1; if(~f[i&1^1][j][k][59])f[i&1][t[j][w[c[i]]]][k][59]=Max(f[i&1][t[j][w[c[i]]]][k][59],f[i&1^1][j][k][59]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][59]=Max(f[i&1][j][t[k][w[c[i]]]][59],f[i&1^1][j][k][59]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][59]=-1; if(~f[i&1^1][j][k][60])f[i&1][t[j][w[c[i]]]][k][60]=Max(f[i&1][t[j][w[c[i]]]][k][60],f[i&1^1][j][k][60]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][60]=Max(f[i&1][j][t[k][w[c[i]]]][60],f[i&1^1][j][k][60]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][60]=-1; if(~f[i&1^1][j][k][61])f[i&1][t[j][w[c[i]]]][k][61]=Max(f[i&1][t[j][w[c[i]]]][k][61],f[i&1^1][j][k][61]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][61]=Max(f[i&1][j][t[k][w[c[i]]]][61],f[i&1^1][j][k][61]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][61]=-1; if(~f[i&1^1][j][k][62])f[i&1][t[j][w[c[i]]]][k][62]=Max(f[i&1][t[j][w[c[i]]]][k][62],f[i&1^1][j][k][62]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][62]=Max(f[i&1][j][t[k][w[c[i]]]][62],f[i&1^1][j][k][62]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][62]=-1; if(~f[i&1^1][j][k][63])f[i&1][t[j][w[c[i]]]][k][63]=Max(f[i&1][t[j][w[c[i]]]][k][63],f[i&1^1][j][k][63]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][63]=Max(f[i&1][j][t[k][w[c[i]]]][63],f[i&1^1][j][k][63]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][63]=-1; if(~f[i&1^1][j][k][64])f[i&1][t[j][w[c[i]]]][k][64]=Max(f[i&1][t[j][w[c[i]]]][k][64],f[i&1^1][j][k][64]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][64]=Max(f[i&1][j][t[k][w[c[i]]]][64],f[i&1^1][j][k][64]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][64]=-1; if(~f[i&1^1][j][k][65])f[i&1][t[j][w[c[i]]]][k][65]=Max(f[i&1][t[j][w[c[i]]]][k][65],f[i&1^1][j][k][65]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][65]=Max(f[i&1][j][t[k][w[c[i]]]][65],f[i&1^1][j][k][65]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][65]=-1; if(~f[i&1^1][j][k][66])f[i&1][t[j][w[c[i]]]][k][66]=Max(f[i&1][t[j][w[c[i]]]][k][66],f[i&1^1][j][k][66]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][66]=Max(f[i&1][j][t[k][w[c[i]]]][66],f[i&1^1][j][k][66]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][66]=-1; if(~f[i&1^1][j][k][67])f[i&1][t[j][w[c[i]]]][k][67]=Max(f[i&1][t[j][w[c[i]]]][k][67],f[i&1^1][j][k][67]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][67]=Max(f[i&1][j][t[k][w[c[i]]]][67],f[i&1^1][j][k][67]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][67]=-1; if(~f[i&1^1][j][k][68])f[i&1][t[j][w[c[i]]]][k][68]=Max(f[i&1][t[j][w[c[i]]]][k][68],f[i&1^1][j][k][68]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][68]=Max(f[i&1][j][t[k][w[c[i]]]][68],f[i&1^1][j][k][68]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][68]=-1; if(~f[i&1^1][j][k][69])f[i&1][t[j][w[c[i]]]][k][69]=Max(f[i&1][t[j][w[c[i]]]][k][69],f[i&1^1][j][k][69]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][69]=Max(f[i&1][j][t[k][w[c[i]]]][69],f[i&1^1][j][k][69]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][69]=-1; if(~f[i&1^1][j][k][70])f[i&1][t[j][w[c[i]]]][k][70]=Max(f[i&1][t[j][w[c[i]]]][k][70],f[i&1^1][j][k][70]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][70]=Max(f[i&1][j][t[k][w[c[i]]]][70],f[i&1^1][j][k][70]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][70]=-1; if(~f[i&1^1][j][k][71])f[i&1][t[j][w[c[i]]]][k][71]=Max(f[i&1][t[j][w[c[i]]]][k][71],f[i&1^1][j][k][71]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][71]=Max(f[i&1][j][t[k][w[c[i]]]][71],f[i&1^1][j][k][71]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][71]=-1; if(~f[i&1^1][j][k][72])f[i&1][t[j][w[c[i]]]][k][72]=Max(f[i&1][t[j][w[c[i]]]][k][72],f[i&1^1][j][k][72]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][72]=Max(f[i&1][j][t[k][w[c[i]]]][72],f[i&1^1][j][k][72]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][72]=-1; if(~f[i&1^1][j][k][73])f[i&1][t[j][w[c[i]]]][k][73]=Max(f[i&1][t[j][w[c[i]]]][k][73],f[i&1^1][j][k][73]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][73]=Max(f[i&1][j][t[k][w[c[i]]]][73],f[i&1^1][j][k][73]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][73]=-1; if(~f[i&1^1][j][k][74])f[i&1][t[j][w[c[i]]]][k][74]=Max(f[i&1][t[j][w[c[i]]]][k][74],f[i&1^1][j][k][74]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][74]=Max(f[i&1][j][t[k][w[c[i]]]][74],f[i&1^1][j][k][74]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][74]=-1; if(~f[i&1^1][j][k][75])f[i&1][t[j][w[c[i]]]][k][75]=Max(f[i&1][t[j][w[c[i]]]][k][75],f[i&1^1][j][k][75]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][75]=Max(f[i&1][j][t[k][w[c[i]]]][75],f[i&1^1][j][k][75]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][75]=-1; if(~f[i&1^1][j][k][76])f[i&1][t[j][w[c[i]]]][k][76]=Max(f[i&1][t[j][w[c[i]]]][k][76],f[i&1^1][j][k][76]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][76]=Max(f[i&1][j][t[k][w[c[i]]]][76],f[i&1^1][j][k][76]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][76]=-1; if(~f[i&1^1][j][k][77])f[i&1][t[j][w[c[i]]]][k][77]=Max(f[i&1][t[j][w[c[i]]]][k][77],f[i&1^1][j][k][77]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][77]=Max(f[i&1][j][t[k][w[c[i]]]][77],f[i&1^1][j][k][77]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][77]=-1; if(~f[i&1^1][j][k][78])f[i&1][t[j][w[c[i]]]][k][78]=Max(f[i&1][t[j][w[c[i]]]][k][78],f[i&1^1][j][k][78]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][78]=Max(f[i&1][j][t[k][w[c[i]]]][78],f[i&1^1][j][k][78]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][78]=-1; if(~f[i&1^1][j][k][79])f[i&1][t[j][w[c[i]]]][k][79]=Max(f[i&1][t[j][w[c[i]]]][k][79],f[i&1^1][j][k][79]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][79]=Max(f[i&1][j][t[k][w[c[i]]]][79],f[i&1^1][j][k][79]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][79]=-1; if(~f[i&1^1][j][k][80])f[i&1][t[j][w[c[i]]]][k][80]=Max(f[i&1][t[j][w[c[i]]]][k][80],f[i&1^1][j][k][80]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][80]=Max(f[i&1][j][t[k][w[c[i]]]][80],f[i&1^1][j][k][80]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][80]=-1; if(~f[i&1^1][j][k][81])f[i&1][t[j][w[c[i]]]][k][81]=Max(f[i&1][t[j][w[c[i]]]][k][81],f[i&1^1][j][k][81]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][81]=Max(f[i&1][j][t[k][w[c[i]]]][81],f[i&1^1][j][k][81]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][81]=-1; if(~f[i&1^1][j][k][82])f[i&1][t[j][w[c[i]]]][k][82]=Max(f[i&1][t[j][w[c[i]]]][k][82],f[i&1^1][j][k][82]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][82]=Max(f[i&1][j][t[k][w[c[i]]]][82],f[i&1^1][j][k][82]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][82]=-1; if(~f[i&1^1][j][k][83])f[i&1][t[j][w[c[i]]]][k][83]=Max(f[i&1][t[j][w[c[i]]]][k][83],f[i&1^1][j][k][83]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][83]=Max(f[i&1][j][t[k][w[c[i]]]][83],f[i&1^1][j][k][83]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][83]=-1; if(~f[i&1^1][j][k][84])f[i&1][t[j][w[c[i]]]][k][84]=Max(f[i&1][t[j][w[c[i]]]][k][84],f[i&1^1][j][k][84]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][84]=Max(f[i&1][j][t[k][w[c[i]]]][84],f[i&1^1][j][k][84]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][84]=-1; if(~f[i&1^1][j][k][85])f[i&1][t[j][w[c[i]]]][k][85]=Max(f[i&1][t[j][w[c[i]]]][k][85],f[i&1^1][j][k][85]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][85]=Max(f[i&1][j][t[k][w[c[i]]]][85],f[i&1^1][j][k][85]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][85]=-1; if(~f[i&1^1][j][k][86])f[i&1][t[j][w[c[i]]]][k][86]=Max(f[i&1][t[j][w[c[i]]]][k][86],f[i&1^1][j][k][86]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][86]=Max(f[i&1][j][t[k][w[c[i]]]][86],f[i&1^1][j][k][86]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][86]=-1; if(~f[i&1^1][j][k][87])f[i&1][t[j][w[c[i]]]][k][87]=Max(f[i&1][t[j][w[c[i]]]][k][87],f[i&1^1][j][k][87]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][87]=Max(f[i&1][j][t[k][w[c[i]]]][87],f[i&1^1][j][k][87]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][87]=-1; if(~f[i&1^1][j][k][88])f[i&1][t[j][w[c[i]]]][k][88]=Max(f[i&1][t[j][w[c[i]]]][k][88],f[i&1^1][j][k][88]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][88]=Max(f[i&1][j][t[k][w[c[i]]]][88],f[i&1^1][j][k][88]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][88]=-1; if(~f[i&1^1][j][k][89])f[i&1][t[j][w[c[i]]]][k][89]=Max(f[i&1][t[j][w[c[i]]]][k][89],f[i&1^1][j][k][89]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][89]=Max(f[i&1][j][t[k][w[c[i]]]][89],f[i&1^1][j][k][89]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][89]=-1; if(~f[i&1^1][j][k][90])f[i&1][t[j][w[c[i]]]][k][90]=Max(f[i&1][t[j][w[c[i]]]][k][90],f[i&1^1][j][k][90]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][90]=Max(f[i&1][j][t[k][w[c[i]]]][90],f[i&1^1][j][k][90]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][90]=-1; if(~f[i&1^1][j][k][91])f[i&1][t[j][w[c[i]]]][k][91]=Max(f[i&1][t[j][w[c[i]]]][k][91],f[i&1^1][j][k][91]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][91]=Max(f[i&1][j][t[k][w[c[i]]]][91],f[i&1^1][j][k][91]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][91]=-1; if(~f[i&1^1][j][k][92])f[i&1][t[j][w[c[i]]]][k][92]=Max(f[i&1][t[j][w[c[i]]]][k][92],f[i&1^1][j][k][92]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][92]=Max(f[i&1][j][t[k][w[c[i]]]][92],f[i&1^1][j][k][92]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][92]=-1; if(~f[i&1^1][j][k][93])f[i&1][t[j][w[c[i]]]][k][93]=Max(f[i&1][t[j][w[c[i]]]][k][93],f[i&1^1][j][k][93]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][93]=Max(f[i&1][j][t[k][w[c[i]]]][93],f[i&1^1][j][k][93]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][93]=-1; if(~f[i&1^1][j][k][94])f[i&1][t[j][w[c[i]]]][k][94]=Max(f[i&1][t[j][w[c[i]]]][k][94],f[i&1^1][j][k][94]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][94]=Max(f[i&1][j][t[k][w[c[i]]]][94],f[i&1^1][j][k][94]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][94]=-1; if(~f[i&1^1][j][k][95])f[i&1][t[j][w[c[i]]]][k][95]=Max(f[i&1][t[j][w[c[i]]]][k][95],f[i&1^1][j][k][95]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][95]=Max(f[i&1][j][t[k][w[c[i]]]][95],f[i&1^1][j][k][95]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][95]=-1; if(~f[i&1^1][j][k][96])f[i&1][t[j][w[c[i]]]][k][96]=Max(f[i&1][t[j][w[c[i]]]][k][96],f[i&1^1][j][k][96]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][96]=Max(f[i&1][j][t[k][w[c[i]]]][96],f[i&1^1][j][k][96]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][96]=-1; if(~f[i&1^1][j][k][97])f[i&1][t[j][w[c[i]]]][k][97]=Max(f[i&1][t[j][w[c[i]]]][k][97],f[i&1^1][j][k][97]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][97]=Max(f[i&1][j][t[k][w[c[i]]]][97],f[i&1^1][j][k][97]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][97]=-1; if(~f[i&1^1][j][k][98])f[i&1][t[j][w[c[i]]]][k][98]=Max(f[i&1][t[j][w[c[i]]]][k][98],f[i&1^1][j][k][98]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][98]=Max(f[i&1][j][t[k][w[c[i]]]][98],f[i&1^1][j][k][98]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][98]=-1; if(~f[i&1^1][j][k][99])f[i&1][t[j][w[c[i]]]][k][99]=Max(f[i&1][t[j][w[c[i]]]][k][99],f[i&1^1][j][k][99]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][99]=Max(f[i&1][j][t[k][w[c[i]]]][99],f[i&1^1][j][k][99]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][99]=-1; if(~f[i&1^1][j][k][100])f[i&1][t[j][w[c[i]]]][k][100]=Max(f[i&1][t[j][w[c[i]]]][k][100],f[i&1^1][j][k][100]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][100]=Max(f[i&1][j][t[k][w[c[i]]]][100],f[i&1^1][j][k][100]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][100]=-1; if(~f[i&1^1][j][k][101])f[i&1][t[j][w[c[i]]]][k][101]=Max(f[i&1][t[j][w[c[i]]]][k][101],f[i&1^1][j][k][101]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][101]=Max(f[i&1][j][t[k][w[c[i]]]][101],f[i&1^1][j][k][101]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][101]=-1; if(~f[i&1^1][j][k][102])f[i&1][t[j][w[c[i]]]][k][102]=Max(f[i&1][t[j][w[c[i]]]][k][102],f[i&1^1][j][k][102]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][102]=Max(f[i&1][j][t[k][w[c[i]]]][102],f[i&1^1][j][k][102]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][102]=-1; if(~f[i&1^1][j][k][103])f[i&1][t[j][w[c[i]]]][k][103]=Max(f[i&1][t[j][w[c[i]]]][k][103],f[i&1^1][j][k][103]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][103]=Max(f[i&1][j][t[k][w[c[i]]]][103],f[i&1^1][j][k][103]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][103]=-1; if(~f[i&1^1][j][k][104])f[i&1][t[j][w[c[i]]]][k][104]=Max(f[i&1][t[j][w[c[i]]]][k][104],f[i&1^1][j][k][104]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][104]=Max(f[i&1][j][t[k][w[c[i]]]][104],f[i&1^1][j][k][104]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][104]=-1; if(~f[i&1^1][j][k][105])f[i&1][t[j][w[c[i]]]][k][105]=Max(f[i&1][t[j][w[c[i]]]][k][105],f[i&1^1][j][k][105]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][105]=Max(f[i&1][j][t[k][w[c[i]]]][105],f[i&1^1][j][k][105]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][105]=-1; if(~f[i&1^1][j][k][106])f[i&1][t[j][w[c[i]]]][k][106]=Max(f[i&1][t[j][w[c[i]]]][k][106],f[i&1^1][j][k][106]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][106]=Max(f[i&1][j][t[k][w[c[i]]]][106],f[i&1^1][j][k][106]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][106]=-1; if(~f[i&1^1][j][k][107])f[i&1][t[j][w[c[i]]]][k][107]=Max(f[i&1][t[j][w[c[i]]]][k][107],f[i&1^1][j][k][107]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][107]=Max(f[i&1][j][t[k][w[c[i]]]][107],f[i&1^1][j][k][107]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][107]=-1; if(~f[i&1^1][j][k][108])f[i&1][t[j][w[c[i]]]][k][108]=Max(f[i&1][t[j][w[c[i]]]][k][108],f[i&1^1][j][k][108]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][108]=Max(f[i&1][j][t[k][w[c[i]]]][108],f[i&1^1][j][k][108]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][108]=-1; if(~f[i&1^1][j][k][109])f[i&1][t[j][w[c[i]]]][k][109]=Max(f[i&1][t[j][w[c[i]]]][k][109],f[i&1^1][j][k][109]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][109]=Max(f[i&1][j][t[k][w[c[i]]]][109],f[i&1^1][j][k][109]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][109]=-1; if(~f[i&1^1][j][k][110])f[i&1][t[j][w[c[i]]]][k][110]=Max(f[i&1][t[j][w[c[i]]]][k][110],f[i&1^1][j][k][110]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][110]=Max(f[i&1][j][t[k][w[c[i]]]][110],f[i&1^1][j][k][110]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][110]=-1; if(~f[i&1^1][j][k][111])f[i&1][t[j][w[c[i]]]][k][111]=Max(f[i&1][t[j][w[c[i]]]][k][111],f[i&1^1][j][k][111]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][111]=Max(f[i&1][j][t[k][w[c[i]]]][111],f[i&1^1][j][k][111]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][111]=-1; if(~f[i&1^1][j][k][112])f[i&1][t[j][w[c[i]]]][k][112]=Max(f[i&1][t[j][w[c[i]]]][k][112],f[i&1^1][j][k][112]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][112]=Max(f[i&1][j][t[k][w[c[i]]]][112],f[i&1^1][j][k][112]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][112]=-1; if(~f[i&1^1][j][k][113])f[i&1][t[j][w[c[i]]]][k][113]=Max(f[i&1][t[j][w[c[i]]]][k][113],f[i&1^1][j][k][113]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][113]=Max(f[i&1][j][t[k][w[c[i]]]][113],f[i&1^1][j][k][113]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][113]=-1; if(~f[i&1^1][j][k][114])f[i&1][t[j][w[c[i]]]][k][114]=Max(f[i&1][t[j][w[c[i]]]][k][114],f[i&1^1][j][k][114]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][114]=Max(f[i&1][j][t[k][w[c[i]]]][114],f[i&1^1][j][k][114]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][114]=-1; if(~f[i&1^1][j][k][115])f[i&1][t[j][w[c[i]]]][k][115]=Max(f[i&1][t[j][w[c[i]]]][k][115],f[i&1^1][j][k][115]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][115]=Max(f[i&1][j][t[k][w[c[i]]]][115],f[i&1^1][j][k][115]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][115]=-1; if(~f[i&1^1][j][k][116])f[i&1][t[j][w[c[i]]]][k][116]=Max(f[i&1][t[j][w[c[i]]]][k][116],f[i&1^1][j][k][116]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][116]=Max(f[i&1][j][t[k][w[c[i]]]][116],f[i&1^1][j][k][116]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][116]=-1; if(~f[i&1^1][j][k][117])f[i&1][t[j][w[c[i]]]][k][117]=Max(f[i&1][t[j][w[c[i]]]][k][117],f[i&1^1][j][k][117]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][117]=Max(f[i&1][j][t[k][w[c[i]]]][117],f[i&1^1][j][k][117]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][117]=-1; if(~f[i&1^1][j][k][118])f[i&1][t[j][w[c[i]]]][k][118]=Max(f[i&1][t[j][w[c[i]]]][k][118],f[i&1^1][j][k][118]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][118]=Max(f[i&1][j][t[k][w[c[i]]]][118],f[i&1^1][j][k][118]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][118]=-1; if(~f[i&1^1][j][k][119])f[i&1][t[j][w[c[i]]]][k][119]=Max(f[i&1][t[j][w[c[i]]]][k][119],f[i&1^1][j][k][119]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][119]=Max(f[i&1][j][t[k][w[c[i]]]][119],f[i&1^1][j][k][119]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][119]=-1; if(~f[i&1^1][j][k][120])f[i&1][t[j][w[c[i]]]][k][120]=Max(f[i&1][t[j][w[c[i]]]][k][120],f[i&1^1][j][k][120]+num[t[j][w[c[i]]]]),f[i&1][j][t[k][w[c[i]]]][120]=Max(f[i&1][j][t[k][w[c[i]]]][120],f[i&1^1][j][k][120]+num[t[k][w[c[i]]]]),f[i&1^1][j][k][120]=-1; } } } } int getans(){ unt ans=0; memset(f,-1,sizeof(f)); for(int i=1;i<=cnt;i++)f[0][1][i][i]=0; slv(); for(int i=1;i<=cnt;i++)for(int j=1;j<=cnt;j++)ans=Max(ans,f[n&1][i][j][i]); 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; }