#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

using namespace std;

const int sigma_size = , maxm = 2e3+;

char s[maxm];

int add[sigma_size], del[sigma_size];

int cost[sigma_size];

int dp[maxm][maxm];

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int n, m;

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

    scanf("%s",s);

    for(int i = n; i--;){

        char ch[];

        scanf("%s",ch);

        int id = *ch-'a';

        scanf("%d%d",add+id,del+id);

        cost[id] = min(add[id],del[id]);

    }

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

        for(int i = ; i+L < m; i++){

            int j = i+L;

            if(s[i] == s[j]){

                dp[i][j] = dp[i+][j-]; // 可能会有i+1 = j, j-1 = i，但是最初是0所以没有影响

            }else {

                dp[i][j] = min(dp[i+][j] + cost[s[i]-'a'], dp[i][j-] + cost[s[j]-'a']) ;

            }

        }

    }

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

    return ;

}