<div class="solution-view">
    <div class="row">
        <div class="col-md-6">
            <p>提交时间：2024-10-09 15:38:06</p>
        </div>
        <div class="col-md-6">
            <p>运行 ID: <a href="/solution/detail?id=33459">33459</a></p>
        </div>
    </div>
    <div class="pre"><p>#include&lt;bits/stdc++.h&gt;
#define up(i,l,r) for(int i=(l);i&lt;=(r);++i)
#define down(i,l,r) for(int i=(l);i&gt;=(r);--i)
#define pi pair&lt;int,int&gt;
#define p1 first
#define p2 second
#define m_p make_pair
#define p_b push_back
#define x1 x114514
#define x2 x214514
using namespace std;
typedef unsigned int ll;
const int maxn=1005;
inline ll read(){
    ll x=0;short t=1;char ch=getchar();
    while(ch&lt;&#039;0&#039;||ch&gt;&#039;9&#039;){if(ch==&#039;-&#039;)t=-1;ch=getchar();}
    while(ch&gt;=&#039;0&#039;&amp;&amp;ch&lt;=&#039;9&#039;)x=x*10+ch-&#039;0&#039;,ch=getchar();
    return x*t;
}int n,m;
string S;
void cmx(ll &amp;x,ll y){
    if((!(~x))||x&lt;y)x=y;
}
struct AC {
    struct nd {
        int son[4],fail;
        ll c;
    }d[155];
    ll dp[2][121][121][121];int ct;
    void ins(string &amp;s,int v){
        int u=0;
        for(char ch:s){
            int o=ch-&#039;a&#039;;
            if(!d[u].son[o])d[u].son[o]=++ct;
            u=d[u].son[o];
        }d[u].c+=v;
    }void bd(){
        queue&lt;int&gt;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;
        memset(dp,-1,sizeof(dp));
        up(i,0,ct)dp[0][0][i][i]=0;
        up(j,0,n-1){
            int op=j&amp;1;
            //memset(dp[!op],-1,sizeof(dp[!op]));
            up(k,0,ct){
                up(l,0,ct){
                    int x1=d[k].son[S[j]-&#039;a&#039;];
                    int x2=d[l].son[S[j]-&#039;a&#039;];
                    if(~dp[op][k][l][0])cmx(dp[!op][x1][l][0],dp[op][k][l][0]+d[x1].c),cmx(dp[!op][k][x2][0],dp[op][k][l][0]+d[x2].c),dp[op][k][l][0]=-1;
                    if(~dp[op][k][l][1])cmx(dp[!op][x1][l][1],dp[op][k][l][1]+d[x1].c),cmx(dp[!op][k][x2][1],dp[op][k][l][1]+d[x2].c),dp[op][k][l][1]=-1;
                    if(~dp[op][k][l][2])cmx(dp[!op][x1][l][2],dp[op][k][l][2]+d[x1].c),cmx(dp[!op][k][x2][2],dp[op][k][l][2]+d[x2].c),dp[op][k][l][2]=-1;
                    if(~dp[op][k][l][3])cmx(dp[!op][x1][l][3],dp[op][k][l][3]+d[x1].c),cmx(dp[!op][k][x2][3],dp[op][k][l][3]+d[x2].c),dp[op][k][l][3]=-1;
                    if(~dp[op][k][l][4])cmx(dp[!op][x1][l][4],dp[op][k][l][4]+d[x1].c),cmx(dp[!op][k][x2][4],dp[op][k][l][4]+d[x2].c),dp[op][k][l][4]=-1;
                    if(~dp[op][k][l][5])cmx(dp[!op][x1][l][5],dp[op][k][l][5]+d[x1].c),cmx(dp[!op][k][x2][5],dp[op][k][l][5]+d[x2].c),dp[op][k][l][5]=-1;
                    if(~dp[op][k][l][6])cmx(dp[!op][x1][l][6],dp[op][k][l][6]+d[x1].c),cmx(dp[!op][k][x2][6],dp[op][k][l][6]+d[x2].c),dp[op][k][l][6]=-1;
                    if(~dp[op][k][l][7])cmx(dp[!op][x1][l][7],dp[op][k][l][7]+d[x1].c),cmx(dp[!op][k][x2][7],dp[op][k][l][7]+d[x2].c),dp[op][k][l][7]=-1;
                    if(~dp[op][k][l][8])cmx(dp[!op][x1][l][8],dp[op][k][l][8]+d[x1].c),cmx(dp[!op][k][x2][8],dp[op][k][l][8]+d[x2].c),dp[op][k][l][8]=-1;
                    if(~dp[op][k][l][9])cmx(dp[!op][x1][l][9],dp[op][k][l][9]+d[x1].c),cmx(dp[!op][k][x2][9],dp[op][k][l][9]+d[x2].c),dp[op][k][l][9]=-1;
                    if(~dp[op][k][l][10])cmx(dp[!op][x1][l][10],dp[op][k][l][10]+d[x1].c),cmx(dp[!op][k][x2][10],dp[op][k][l][10]+d[x2].c),dp[op][k][l][10]=-1;
                    if(~dp[op][k][l][11])cmx(dp[!op][x1][l][11],dp[op][k][l][11]+d[x1].c),cmx(dp[!op][k][x2][11],dp[op][k][l][11]+d[x2].c),dp[op][k][l][11]=-1;
                    if(~dp[op][k][l][12])cmx(dp[!op][x1][l][12],dp[op][k][l][12]+d[x1].c),cmx(dp[!op][k][x2][12],dp[op][k][l][12]+d[x2].c),dp[op][k][l][12]=-1;
                    if(~dp[op][k][l][13])cmx(dp[!op][x1][l][13],dp[op][k][l][13]+d[x1].c),cmx(dp[!op][k][x2][13],dp[op][k][l][13]+d[x2].c),dp[op][k][l][13]=-1;
                    if(~dp[op][k][l][14])cmx(dp[!op][x1][l][14],dp[op][k][l][14]+d[x1].c),cmx(dp[!op][k][x2][14],dp[op][k][l][14]+d[x2].c),dp[op][k][l][14]=-1;
                    if(~dp[op][k][l][15])cmx(dp[!op][x1][l][15],dp[op][k][l][15]+d[x1].c),cmx(dp[!op][k][x2][15],dp[op][k][l][15]+d[x2].c),dp[op][k][l][15]=-1;
                    if(~dp[op][k][l][16])cmx(dp[!op][x1][l][16],dp[op][k][l][16]+d[x1].c),cmx(dp[!op][k][x2][16],dp[op][k][l][16]+d[x2].c),dp[op][k][l][16]=-1;
                    if(~dp[op][k][l][17])cmx(dp[!op][x1][l][17],dp[op][k][l][17]+d[x1].c),cmx(dp[!op][k][x2][17],dp[op][k][l][17]+d[x2].c),dp[op][k][l][17]=-1;
                    if(~dp[op][k][l][18])cmx(dp[!op][x1][l][18],dp[op][k][l][18]+d[x1].c),cmx(dp[!op][k][x2][18],dp[op][k][l][18]+d[x2].c),dp[op][k][l][18]=-1;
                    if(~dp[op][k][l][19])cmx(dp[!op][x1][l][19],dp[op][k][l][19]+d[x1].c),cmx(dp[!op][k][x2][19],dp[op][k][l][19]+d[x2].c),dp[op][k][l][19]=-1;
                    if(~dp[op][k][l][20])cmx(dp[!op][x1][l][20],dp[op][k][l][20]+d[x1].c),cmx(dp[!op][k][x2][20],dp[op][k][l][20]+d[x2].c),dp[op][k][l][20]=-1;
                    if(~dp[op][k][l][21])cmx(dp[!op][x1][l][21],dp[op][k][l][21]+d[x1].c),cmx(dp[!op][k][x2][21],dp[op][k][l][21]+d[x2].c),dp[op][k][l][21]=-1;
                    if(~dp[op][k][l][22])cmx(dp[!op][x1][l][22],dp[op][k][l][22]+d[x1].c),cmx(dp[!op][k][x2][22],dp[op][k][l][22]+d[x2].c),dp[op][k][l][22]=-1;
                    if(~dp[op][k][l][23])cmx(dp[!op][x1][l][23],dp[op][k][l][23]+d[x1].c),cmx(dp[!op][k][x2][23],dp[op][k][l][23]+d[x2].c),dp[op][k][l][23]=-1;
                    if(~dp[op][k][l][24])cmx(dp[!op][x1][l][24],dp[op][k][l][24]+d[x1].c),cmx(dp[!op][k][x2][24],dp[op][k][l][24]+d[x2].c),dp[op][k][l][24]=-1;
                    if(~dp[op][k][l][25])cmx(dp[!op][x1][l][25],dp[op][k][l][25]+d[x1].c),cmx(dp[!op][k][x2][25],dp[op][k][l][25]+d[x2].c),dp[op][k][l][25]=-1;
                    if(~dp[op][k][l][26])cmx(dp[!op][x1][l][26],dp[op][k][l][26]+d[x1].c),cmx(dp[!op][k][x2][26],dp[op][k][l][26]+d[x2].c),dp[op][k][l][26]=-1;
                    if(~dp[op][k][l][27])cmx(dp[!op][x1][l][27],dp[op][k][l][27]+d[x1].c),cmx(dp[!op][k][x2][27],dp[op][k][l][27]+d[x2].c),dp[op][k][l][27]=-1;
                    if(~dp[op][k][l][28])cmx(dp[!op][x1][l][28],dp[op][k][l][28]+d[x1].c),cmx(dp[!op][k][x2][28],dp[op][k][l][28]+d[x2].c),dp[op][k][l][28]=-1;
                    if(~dp[op][k][l][29])cmx(dp[!op][x1][l][29],dp[op][k][l][29]+d[x1].c),cmx(dp[!op][k][x2][29],dp[op][k][l][29]+d[x2].c),dp[op][k][l][29]=-1;
                    if(~dp[op][k][l][30])cmx(dp[!op][x1][l][30],dp[op][k][l][30]+d[x1].c),cmx(dp[!op][k][x2][30],dp[op][k][l][30]+d[x2].c),dp[op][k][l][30]=-1;
                    if(~dp[op][k][l][31])cmx(dp[!op][x1][l][31],dp[op][k][l][31]+d[x1].c),cmx(dp[!op][k][x2][31],dp[op][k][l][31]+d[x2].c),dp[op][k][l][31]=-1;
                    if(~dp[op][k][l][32])cmx(dp[!op][x1][l][32],dp[op][k][l][32]+d[x1].c),cmx(dp[!op][k][x2][32],dp[op][k][l][32]+d[x2].c),dp[op][k][l][32]=-1;
                    if(~dp[op][k][l][33])cmx(dp[!op][x1][l][33],dp[op][k][l][33]+d[x1].c),cmx(dp[!op][k][x2][33],dp[op][k][l][33]+d[x2].c),dp[op][k][l][33]=-1;
                    if(~dp[op][k][l][34])cmx(dp[!op][x1][l][34],dp[op][k][l][34]+d[x1].c),cmx(dp[!op][k][x2][34],dp[op][k][l][34]+d[x2].c),dp[op][k][l][34]=-1;
                    if(~dp[op][k][l][35])cmx(dp[!op][x1][l][35],dp[op][k][l][35]+d[x1].c),cmx(dp[!op][k][x2][35],dp[op][k][l][35]+d[x2].c),dp[op][k][l][35]=-1;
                    if(~dp[op][k][l][36])cmx(dp[!op][x1][l][36],dp[op][k][l][36]+d[x1].c),cmx(dp[!op][k][x2][36],dp[op][k][l][36]+d[x2].c),dp[op][k][l][36]=-1;
                    if(~dp[op][k][l][37])cmx(dp[!op][x1][l][37],dp[op][k][l][37]+d[x1].c),cmx(dp[!op][k][x2][37],dp[op][k][l][37]+d[x2].c),dp[op][k][l][37]=-1;
                    if(~dp[op][k][l][38])cmx(dp[!op][x1][l][38],dp[op][k][l][38]+d[x1].c),cmx(dp[!op][k][x2][38],dp[op][k][l][38]+d[x2].c),dp[op][k][l][38]=-1;
                    if(~dp[op][k][l][39])cmx(dp[!op][x1][l][39],dp[op][k][l][39]+d[x1].c),cmx(dp[!op][k][x2][39],dp[op][k][l][39]+d[x2].c),dp[op][k][l][39]=-1;
                    if(~dp[op][k][l][40])cmx(dp[!op][x1][l][40],dp[op][k][l][40]+d[x1].c),cmx(dp[!op][k][x2][40],dp[op][k][l][40]+d[x2].c),dp[op][k][l][40]=-1;
                    if(~dp[op][k][l][41])cmx(dp[!op][x1][l][41],dp[op][k][l][41]+d[x1].c),cmx(dp[!op][k][x2][41],dp[op][k][l][41]+d[x2].c),dp[op][k][l][41]=-1;
                    if(~dp[op][k][l][42])cmx(dp[!op][x1][l][42],dp[op][k][l][42]+d[x1].c),cmx(dp[!op][k][x2][42],dp[op][k][l][42]+d[x2].c),dp[op][k][l][42]=-1;
                    if(~dp[op][k][l][43])cmx(dp[!op][x1][l][43],dp[op][k][l][43]+d[x1].c),cmx(dp[!op][k][x2][43],dp[op][k][l][43]+d[x2].c),dp[op][k][l][43]=-1;
                    if(~dp[op][k][l][44])cmx(dp[!op][x1][l][44],dp[op][k][l][44]+d[x1].c),cmx(dp[!op][k][x2][44],dp[op][k][l][44]+d[x2].c),dp[op][k][l][44]=-1;
                    if(~dp[op][k][l][45])cmx(dp[!op][x1][l][45],dp[op][k][l][45]+d[x1].c),cmx(dp[!op][k][x2][45],dp[op][k][l][45]+d[x2].c),dp[op][k][l][45]=-1;
                    if(~dp[op][k][l][46])cmx(dp[!op][x1][l][46],dp[op][k][l][46]+d[x1].c),cmx(dp[!op][k][x2][46],dp[op][k][l][46]+d[x2].c),dp[op][k][l][46]=-1;
                    if(~dp[op][k][l][47])cmx(dp[!op][x1][l][47],dp[op][k][l][47]+d[x1].c),cmx(dp[!op][k][x2][47],dp[op][k][l][47]+d[x2].c),dp[op][k][l][47]=-1;
                    if(~dp[op][k][l][48])cmx(dp[!op][x1][l][48],dp[op][k][l][48]+d[x1].c),cmx(dp[!op][k][x2][48],dp[op][k][l][48]+d[x2].c),dp[op][k][l][48]=-1;
                    if(~dp[op][k][l][49])cmx(dp[!op][x1][l][49],dp[op][k][l][49]+d[x1].c),cmx(dp[!op][k][x2][49],dp[op][k][l][49]+d[x2].c),dp[op][k][l][49]=-1;
                    if(~dp[op][k][l][50])cmx(dp[!op][x1][l][50],dp[op][k][l][50]+d[x1].c),cmx(dp[!op][k][x2][50],dp[op][k][l][50]+d[x2].c),dp[op][k][l][50]=-1;
                    if(~dp[op][k][l][51])cmx(dp[!op][x1][l][51],dp[op][k][l][51]+d[x1].c),cmx(dp[!op][k][x2][51],dp[op][k][l][51]+d[x2].c),dp[op][k][l][51]=-1;
                    if(~dp[op][k][l][52])cmx(dp[!op][x1][l][52],dp[op][k][l][52]+d[x1].c),cmx(dp[!op][k][x2][52],dp[op][k][l][52]+d[x2].c),dp[op][k][l][52]=-1;
                    if(~dp[op][k][l][53])cmx(dp[!op][x1][l][53],dp[op][k][l][53]+d[x1].c),cmx(dp[!op][k][x2][53],dp[op][k][l][53]+d[x2].c),dp[op][k][l][53]=-1;
                    if(~dp[op][k][l][54])cmx(dp[!op][x1][l][54],dp[op][k][l][54]+d[x1].c),cmx(dp[!op][k][x2][54],dp[op][k][l][54]+d[x2].c),dp[op][k][l][54]=-1;
                    if(~dp[op][k][l][55])cmx(dp[!op][x1][l][55],dp[op][k][l][55]+d[x1].c),cmx(dp[!op][k][x2][55],dp[op][k][l][55]+d[x2].c),dp[op][k][l][55]=-1;
                    if(~dp[op][k][l][56])cmx(dp[!op][x1][l][56],dp[op][k][l][56]+d[x1].c),cmx(dp[!op][k][x2][56],dp[op][k][l][56]+d[x2].c),dp[op][k][l][56]=-1;
                    if(~dp[op][k][l][57])cmx(dp[!op][x1][l][57],dp[op][k][l][57]+d[x1].c),cmx(dp[!op][k][x2][57],dp[op][k][l][57]+d[x2].c),dp[op][k][l][57]=-1;
                    if(~dp[op][k][l][58])cmx(dp[!op][x1][l][58],dp[op][k][l][58]+d[x1].c),cmx(dp[!op][k][x2][58],dp[op][k][l][58]+d[x2].c),dp[op][k][l][58]=-1;
                    if(~dp[op][k][l][59])cmx(dp[!op][x1][l][59],dp[op][k][l][59]+d[x1].c),cmx(dp[!op][k][x2][59],dp[op][k][l][59]+d[x2].c),dp[op][k][l][59]=-1;
                    if(~dp[op][k][l][60])cmx(dp[!op][x1][l][60],dp[op][k][l][60]+d[x1].c),cmx(dp[!op][k][x2][60],dp[op][k][l][60]+d[x2].c),dp[op][k][l][60]=-1;
                    if(~dp[op][k][l][61])cmx(dp[!op][x1][l][61],dp[op][k][l][61]+d[x1].c),cmx(dp[!op][k][x2][61],dp[op][k][l][61]+d[x2].c),dp[op][k][l][61]=-1;
                    if(~dp[op][k][l][62])cmx(dp[!op][x1][l][62],dp[op][k][l][62]+d[x1].c),cmx(dp[!op][k][x2][62],dp[op][k][l][62]+d[x2].c),dp[op][k][l][62]=-1;
                    if(~dp[op][k][l][63])cmx(dp[!op][x1][l][63],dp[op][k][l][63]+d[x1].c),cmx(dp[!op][k][x2][63],dp[op][k][l][63]+d[x2].c),dp[op][k][l][63]=-1;
                    if(~dp[op][k][l][64])cmx(dp[!op][x1][l][64],dp[op][k][l][64]+d[x1].c),cmx(dp[!op][k][x2][64],dp[op][k][l][64]+d[x2].c),dp[op][k][l][64]=-1;
                    if(~dp[op][k][l][65])cmx(dp[!op][x1][l][65],dp[op][k][l][65]+d[x1].c),cmx(dp[!op][k][x2][65],dp[op][k][l][65]+d[x2].c),dp[op][k][l][65]=-1;
                    if(~dp[op][k][l][66])cmx(dp[!op][x1][l][66],dp[op][k][l][66]+d[x1].c),cmx(dp[!op][k][x2][66],dp[op][k][l][66]+d[x2].c),dp[op][k][l][66]=-1;
                    if(~dp[op][k][l][67])cmx(dp[!op][x1][l][67],dp[op][k][l][67]+d[x1].c),cmx(dp[!op][k][x2][67],dp[op][k][l][67]+d[x2].c),dp[op][k][l][67]=-1;
                    if(~dp[op][k][l][68])cmx(dp[!op][x1][l][68],dp[op][k][l][68]+d[x1].c),cmx(dp[!op][k][x2][68],dp[op][k][l][68]+d[x2].c),dp[op][k][l][68]=-1;
                    if(~dp[op][k][l][69])cmx(dp[!op][x1][l][69],dp[op][k][l][69]+d[x1].c),cmx(dp[!op][k][x2][69],dp[op][k][l][69]+d[x2].c),dp[op][k][l][69]=-1;
                    if(~dp[op][k][l][70])cmx(dp[!op][x1][l][70],dp[op][k][l][70]+d[x1].c),cmx(dp[!op][k][x2][70],dp[op][k][l][70]+d[x2].c),dp[op][k][l][70]=-1;
                    if(~dp[op][k][l][71])cmx(dp[!op][x1][l][71],dp[op][k][l][71]+d[x1].c),cmx(dp[!op][k][x2][71],dp[op][k][l][71]+d[x2].c),dp[op][k][l][71]=-1;
                    if(~dp[op][k][l][72])cmx(dp[!op][x1][l][72],dp[op][k][l][72]+d[x1].c),cmx(dp[!op][k][x2][72],dp[op][k][l][72]+d[x2].c),dp[op][k][l][72]=-1;
                    if(~dp[op][k][l][73])cmx(dp[!op][x1][l][73],dp[op][k][l][73]+d[x1].c),cmx(dp[!op][k][x2][73],dp[op][k][l][73]+d[x2].c),dp[op][k][l][73]=-1;
                    if(~dp[op][k][l][74])cmx(dp[!op][x1][l][74],dp[op][k][l][74]+d[x1].c),cmx(dp[!op][k][x2][74],dp[op][k][l][74]+d[x2].c),dp[op][k][l][74]=-1;
                    if(~dp[op][k][l][75])cmx(dp[!op][x1][l][75],dp[op][k][l][75]+d[x1].c),cmx(dp[!op][k][x2][75],dp[op][k][l][75]+d[x2].c),dp[op][k][l][75]=-1;
                    if(~dp[op][k][l][76])cmx(dp[!op][x1][l][76],dp[op][k][l][76]+d[x1].c),cmx(dp[!op][k][x2][76],dp[op][k][l][76]+d[x2].c),dp[op][k][l][76]=-1;
                    if(~dp[op][k][l][77])cmx(dp[!op][x1][l][77],dp[op][k][l][77]+d[x1].c),cmx(dp[!op][k][x2][77],dp[op][k][l][77]+d[x2].c),dp[op][k][l][77]=-1;
                    if(~dp[op][k][l][78])cmx(dp[!op][x1][l][78],dp[op][k][l][78]+d[x1].c),cmx(dp[!op][k][x2][78],dp[op][k][l][78]+d[x2].c),dp[op][k][l][78]=-1;
                    if(~dp[op][k][l][79])cmx(dp[!op][x1][l][79],dp[op][k][l][79]+d[x1].c),cmx(dp[!op][k][x2][79],dp[op][k][l][79]+d[x2].c),dp[op][k][l][79]=-1;
                    if(~dp[op][k][l][80])cmx(dp[!op][x1][l][80],dp[op][k][l][80]+d[x1].c),cmx(dp[!op][k][x2][80],dp[op][k][l][80]+d[x2].c),dp[op][k][l][80]=-1;
                    if(~dp[op][k][l][81])cmx(dp[!op][x1][l][81],dp[op][k][l][81]+d[x1].c),cmx(dp[!op][k][x2][81],dp[op][k][l][81]+d[x2].c),dp[op][k][l][81]=-1;
                    if(~dp[op][k][l][82])cmx(dp[!op][x1][l][82],dp[op][k][l][82]+d[x1].c),cmx(dp[!op][k][x2][82],dp[op][k][l][82]+d[x2].c),dp[op][k][l][82]=-1;
                    if(~dp[op][k][l][83])cmx(dp[!op][x1][l][83],dp[op][k][l][83]+d[x1].c),cmx(dp[!op][k][x2][83],dp[op][k][l][83]+d[x2].c),dp[op][k][l][83]=-1;
                    if(~dp[op][k][l][84])cmx(dp[!op][x1][l][84],dp[op][k][l][84]+d[x1].c),cmx(dp[!op][k][x2][84],dp[op][k][l][84]+d[x2].c),dp[op][k][l][84]=-1;
                    if(~dp[op][k][l][85])cmx(dp[!op][x1][l][85],dp[op][k][l][85]+d[x1].c),cmx(dp[!op][k][x2][85],dp[op][k][l][85]+d[x2].c),dp[op][k][l][85]=-1;
                    if(~dp[op][k][l][86])cmx(dp[!op][x1][l][86],dp[op][k][l][86]+d[x1].c),cmx(dp[!op][k][x2][86],dp[op][k][l][86]+d[x2].c),dp[op][k][l][86]=-1;
                    if(~dp[op][k][l][87])cmx(dp[!op][x1][l][87],dp[op][k][l][87]+d[x1].c),cmx(dp[!op][k][x2][87],dp[op][k][l][87]+d[x2].c),dp[op][k][l][87]=-1;
                    if(~dp[op][k][l][88])cmx(dp[!op][x1][l][88],dp[op][k][l][88]+d[x1].c),cmx(dp[!op][k][x2][88],dp[op][k][l][88]+d[x2].c),dp[op][k][l][88]=-1;
                    if(~dp[op][k][l][89])cmx(dp[!op][x1][l][89],dp[op][k][l][89]+d[x1].c),cmx(dp[!op][k][x2][89],dp[op][k][l][89]+d[x2].c),dp[op][k][l][89]=-1;
                    if(~dp[op][k][l][90])cmx(dp[!op][x1][l][90],dp[op][k][l][90]+d[x1].c),cmx(dp[!op][k][x2][90],dp[op][k][l][90]+d[x2].c),dp[op][k][l][90]=-1;
                    if(~dp[op][k][l][91])cmx(dp[!op][x1][l][91],dp[op][k][l][91]+d[x1].c),cmx(dp[!op][k][x2][91],dp[op][k][l][91]+d[x2].c),dp[op][k][l][91]=-1;
                    if(~dp[op][k][l][92])cmx(dp[!op][x1][l][92],dp[op][k][l][92]+d[x1].c),cmx(dp[!op][k][x2][92],dp[op][k][l][92]+d[x2].c),dp[op][k][l][92]=-1;
                    if(~dp[op][k][l][93])cmx(dp[!op][x1][l][93],dp[op][k][l][93]+d[x1].c),cmx(dp[!op][k][x2][93],dp[op][k][l][93]+d[x2].c),dp[op][k][l][93]=-1;
                    if(~dp[op][k][l][94])cmx(dp[!op][x1][l][94],dp[op][k][l][94]+d[x1].c),cmx(dp[!op][k][x2][94],dp[op][k][l][94]+d[x2].c),dp[op][k][l][94]=-1;
                    if(~dp[op][k][l][95])cmx(dp[!op][x1][l][95],dp[op][k][l][95]+d[x1].c),cmx(dp[!op][k][x2][95],dp[op][k][l][95]+d[x2].c),dp[op][k][l][95]=-1;
                    if(~dp[op][k][l][96])cmx(dp[!op][x1][l][96],dp[op][k][l][96]+d[x1].c),cmx(dp[!op][k][x2][96],dp[op][k][l][96]+d[x2].c),dp[op][k][l][96]=-1;
                    if(~dp[op][k][l][97])cmx(dp[!op][x1][l][97],dp[op][k][l][97]+d[x1].c),cmx(dp[!op][k][x2][97],dp[op][k][l][97]+d[x2].c),dp[op][k][l][97]=-1;
                    if(~dp[op][k][l][98])cmx(dp[!op][x1][l][98],dp[op][k][l][98]+d[x1].c),cmx(dp[!op][k][x2][98],dp[op][k][l][98]+d[x2].c),dp[op][k][l][98]=-1;
                    if(~dp[op][k][l][99])cmx(dp[!op][x1][l][99],dp[op][k][l][99]+d[x1].c),cmx(dp[!op][k][x2][99],dp[op][k][l][99]+d[x2].c),dp[op][k][l][99]=-1;
                    if(~dp[op][k][l][100])cmx(dp[!op][x1][l][100],dp[op][k][l][100]+d[x1].c),cmx(dp[!op][k][x2][100],dp[op][k][l][100]+d[x2].c),dp[op][k][l][100]=-1;
                    if(~dp[op][k][l][101])cmx(dp[!op][x1][l][101],dp[op][k][l][101]+d[x1].c),cmx(dp[!op][k][x2][101],dp[op][k][l][101]+d[x2].c),dp[op][k][l][101]=-1;
                    if(~dp[op][k][l][102])cmx(dp[!op][x1][l][102],dp[op][k][l][102]+d[x1].c),cmx(dp[!op][k][x2][102],dp[op][k][l][102]+d[x2].c),dp[op][k][l][102]=-1;
                    if(~dp[op][k][l][103])cmx(dp[!op][x1][l][103],dp[op][k][l][103]+d[x1].c),cmx(dp[!op][k][x2][103],dp[op][k][l][103]+d[x2].c),dp[op][k][l][103]=-1;
                    if(~dp[op][k][l][104])cmx(dp[!op][x1][l][104],dp[op][k][l][104]+d[x1].c),cmx(dp[!op][k][x2][104],dp[op][k][l][104]+d[x2].c),dp[op][k][l][104]=-1;
                    if(~dp[op][k][l][105])cmx(dp[!op][x1][l][105],dp[op][k][l][105]+d[x1].c),cmx(dp[!op][k][x2][105],dp[op][k][l][105]+d[x2].c),dp[op][k][l][105]=-1;
                    if(~dp[op][k][l][106])cmx(dp[!op][x1][l][106],dp[op][k][l][106]+d[x1].c),cmx(dp[!op][k][x2][106],dp[op][k][l][106]+d[x2].c),dp[op][k][l][106]=-1;
                    if(~dp[op][k][l][107])cmx(dp[!op][x1][l][107],dp[op][k][l][107]+d[x1].c),cmx(dp[!op][k][x2][107],dp[op][k][l][107]+d[x2].c),dp[op][k][l][107]=-1;
                    if(~dp[op][k][l][108])cmx(dp[!op][x1][l][108],dp[op][k][l][108]+d[x1].c),cmx(dp[!op][k][x2][108],dp[op][k][l][108]+d[x2].c),dp[op][k][l][108]=-1;
                    if(~dp[op][k][l][109])cmx(dp[!op][x1][l][109],dp[op][k][l][109]+d[x1].c),cmx(dp[!op][k][x2][109],dp[op][k][l][109]+d[x2].c),dp[op][k][l][109]=-1;
                    if(~dp[op][k][l][110])cmx(dp[!op][x1][l][110],dp[op][k][l][110]+d[x1].c),cmx(dp[!op][k][x2][110],dp[op][k][l][110]+d[x2].c),dp[op][k][l][110]=-1;
                    if(~dp[op][k][l][111])cmx(dp[!op][x1][l][111],dp[op][k][l][111]+d[x1].c),cmx(dp[!op][k][x2][111],dp[op][k][l][111]+d[x2].c),dp[op][k][l][111]=-1;
                    if(~dp[op][k][l][112])cmx(dp[!op][x1][l][112],dp[op][k][l][112]+d[x1].c),cmx(dp[!op][k][x2][112],dp[op][k][l][112]+d[x2].c),dp[op][k][l][112]=-1;
                    if(~dp[op][k][l][113])cmx(dp[!op][x1][l][113],dp[op][k][l][113]+d[x1].c),cmx(dp[!op][k][x2][113],dp[op][k][l][113]+d[x2].c),dp[op][k][l][113]=-1;
                    if(~dp[op][k][l][114])cmx(dp[!op][x1][l][114],dp[op][k][l][114]+d[x1].c),cmx(dp[!op][k][x2][114],dp[op][k][l][114]+d[x2].c),dp[op][k][l][114]=-1;
                    if(~dp[op][k][l][115])cmx(dp[!op][x1][l][115],dp[op][k][l][115]+d[x1].c),cmx(dp[!op][k][x2][115],dp[op][k][l][115]+d[x2].c),dp[op][k][l][115]=-1;
                    if(~dp[op][k][l][116])cmx(dp[!op][x1][l][116],dp[op][k][l][116]+d[x1].c),cmx(dp[!op][k][x2][116],dp[op][k][l][116]+d[x2].c),dp[op][k][l][116]=-1;
                    if(~dp[op][k][l][117])cmx(dp[!op][x1][l][117],dp[op][k][l][117]+d[x1].c),cmx(dp[!op][k][x2][117],dp[op][k][l][117]+d[x2].c),dp[op][k][l][117]=-1;
                    if(~dp[op][k][l][118])cmx(dp[!op][x1][l][118],dp[op][k][l][118]+d[x1].c),cmx(dp[!op][k][x2][118],dp[op][k][l][118]+d[x2].c),dp[op][k][l][118]=-1;
                    if(~dp[op][k][l][119])cmx(dp[!op][x1][l][119],dp[op][k][l][119]+d[x1].c),cmx(dp[!op][k][x2][119],dp[op][k][l][119]+d[x2].c),dp[op][k][l][119]=-1;
                    if(~dp[op][k][l][120])cmx(dp[!op][x1][l][120],dp[op][k][l][120]+d[x1].c),cmx(dp[!op][k][x2][120],dp[op][k][l][120]+d[x2].c),dp[op][k][l][120]=-1;
                }
            }
        }int op=n&amp;1;up(i,0,ct)up(j,0,ct)if(~dp[n&amp;1][i][j][i])res=max(res,dp[n&amp;1][i][j][i]);
        return res;
    }
}T;
char g(char ch){
    if(ch==&#039;O&#039;)return &#039;a&#039;;
    if(ch==&#039;I&#039;)return &#039;b&#039;;
    if(ch==&#039;L&#039;)return &#039;c&#039;;
    return &#039;d&#039;;
}
void slv(){
    cin&gt;&gt;n&gt;&gt;m;
    cin&gt;&gt;S;for(char &amp;ch:S)ch=g(ch);
    up(i,1,m){
        int len=0,val=0;string t;
        cin&gt;&gt;len&gt;&gt;val&gt;&gt;t;for(char &amp;ch:t)ch=g(ch);
        T.ins(t,val);
    }T.bd();
    cout&lt;&lt;T.calc_dp();
}signed main(){
    //freopen(&quot;tetr.in&quot;,&quot;r&quot;,stdin);
    //freopen(&quot;tetr.out&quot;,&quot;w&quot;,stdout);
    slv();
    fclose(stdin);
    fclose(stdout);
    //cerr&lt;&lt;clock()*1.0/CLOCKS_PER_SEC&lt;&lt;&quot;s\n&quot;;
    return 0;
}</p></div>
</div>
<script type="text/javascript">
    (function ($) {
        $(document).ready(function () {
            $('.pre p').each(function(i, block) {  // use <pre><p>
                hljs.highlightBlock(block);
            });
        })
    })(jQuery);
</script>