include <bits/stdc++.h>

using namespace std; long long dp[2005][2005]; int cost[26];

int main() {

int n, m;
cin >> n >> m;
string s;
cin >> s;
for (int i = 0; i < n; ++i) {
	char c;
	int x, y;
	cin >> c >> x >> y;
	cost[c - 'a'] = min(x, y);
}
for (int i = 2; i <= m; ++i) {
	for (int l = 0; l <= m - i; l++) {
		int r = l + i - 1;

		if (s[l] == s[r]) {
			dp[l][r] = dp[l + 1][r - 1];
		} else {
			dp[l][r] = min(dp[l + 1][r] + cost[s[l] - 'a'], dp[l][r - 1] + cost[s[r] - 'a']);
		}
	}
}

cout << dp[0][m - 1] << endl;

return 0;

}