#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

int n,m,s[maxn],a[],f[maxn][maxn];

char ss[maxn];

int main(){

    scanf("%d%d%s",&n,&m,ss+);

    for(int i=;i<=m;i++)s[i]=ss[i]-'a';

    int b,c;

    for(int i=;i<=n;i++){

        scanf("%s",ss+);

        scanf("%d%d",&b,&c);

        a[ss[]-'a']=min(b,c);

    }

    memset(f,0x3f,sizeof(f));

    for(int i=;i<=m;i++)f[i][i]=,f[i][i+]=f[i+][i]=;//

    for(int p=;p<=m;p++){

        for(int i=;i<=m-p+;i++){

            int j=i+p-;

            f[i][j]=min(f[i+][j]+a[s[i]],f[i][j-]+a[s[j]]);

            if(s[i]==s[j])f[i][j]=min(f[i][j],f[i+][j-]);

        }

    }

    printf("%d",f[][m]);

    return ;

}