#include<bits/stdc++.h>
using namespace std;
const int maxn=4005;
const int inf=0x3f3f3f3f;
int n,m;
char s[maxn];
int dp[maxn][maxn],a[205][2];
int main()
{
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	char st;
	int x,y;
	for(int i=1;i<=n;i++)
	{
		cin>>st;
		scanf("%d%d",&x,&y);
		a[(int)(st)][0]=y;
		a[(int)(st)][1]=x;
	}
//	memset(dp,0x3f3f3f,sizeof(dp));
///	for(int i=1;i<=m;i++)dp[i][i]=0;
	for(int len=2;len<=m;len++)
		for(int i=1;i+len-1<=m;len++)
		{
			int j=i+len-1;
			if(s[i]==s[j])
			{
				if(i+1==j)dp[i][j]=0;
				else dp[i][j]=dp[i+1][j-1];
			}
			else
			{
				dp[i][j]=min(min(min(dp[i][j-1]+a[(int)(s[j])][0],dp[i][j-1]+a[(int)(s[j])][1]),dp[i+1][j]+a[(int)(s[i])][0]),dp[i+1][j]+a[(int)(s[i])][1]);
			}
		}
	printf("%d",dp[1][m]);
	return 0;
}