#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 2010;
char s[N];

int n, m;

int f[N][N];

struct Str
{
	int add, remove;
}ch[28];

int main()
{
	cin >> n >> m;
	
	cin >> (s + 1);
	
	for (int i = 1; i <= n; i ++ )
	{
		char awsl;
		cin >> awsl;
		cin >> ch[awsl - 'a'].add >> ch[awsl - 'a'].remove;
	}
		
	memset(f, 0x3f, sizeof f);
	
	for (int i = 1; i <= m; i ++ )
		f[i][i] = 0;
		
	for (int l = 1; l <= m; l ++ )
		for (int len = 1; l + len - 1 <= m; len ++ )
		{
			int r = l + len - 1;
			if (s[l] == s[r])
				f[l][r] = min(f[l][r], f[l + 1][r - 1]);
			else
			{
				f[l][r] = min(f[l][r], f[l + 1][r] + ch[s[l] - 'a'].add);
				f[l][r] = min(f[l][r], f[l][r - 1] + ch[s[r] - 'a'].add);
				f[l][r] = min(f[l][r], f[l + 1][r] + ch[s[l] - 'a'].remove);
				f[l][r] = min(f[l][r], f[l][r - 1] + ch[s[r] - 'a'].remove);
			}
		}
		
	cout << f[1][m] << endl;
	
	return 0;
}