#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

char s[],ch;

int n,m,a,b;

int add[],dp[][];

int main(){

    scanf("%d%d",&n,&m);

    scanf("%s",s);

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

        cin>>ch;

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

        add[ch]=min(a,b);

    }

    for (int k=;k<m;k++)

        for (int i=,j=k;j<m;i++,j++){

            dp[i][j]=0x7fffffff;

            if (s[i]==s[j]) dp[i][j]=dp[i+][j-];

            else{

                dp[i][j]=min(dp[i+][j]+add[s[i]],dp[i][j]);

                dp[i][j]=min(dp[i][j-]+add[s[j]],dp[i][j]);

            }

        }

    printf("%d\n",dp[][m-]);

    return ;

}