AC

#include <iostream>
#include <vector>
#include <climits>
#include <unordered_map>

using namespace std; int main() {

int n, m;
cin >> n >> m;
string s;
cin >> s;
unordered_map<char, int> add_cost, del_cost;
for (int i = 0; i < n; ++i) {
    char c;
    int add, del;
    cin >> c >> add >> del;
    add_cost[c] = add;
    del_cost[c] = del;
}
vector<vector<int>> dp(m, vector<int>(m, 0));
for (int len = 2; len <= m; ++len) {
    for (int i = 0; i <= m - len; ++i) {
        int j = i + len - 1;
        if (s[i] == s[j]) {
            dp[i][j] = (len == 2) ? 0 : dp[i+1][j-1];
        } else {
            int add_left = add_cost[s[i]] + dp[i+1][j];
            int add_right = add_cost[s[j]] + dp[i][j-1];
            int del_left = del_cost[s[i]] + dp[i+1][j];
            int del_right = del_cost[s[j]] + dp[i][j-1];
            dp[i][j] = min(min(add_left, add_right), min(del_left, del_right));
        }
    }
}
cout << dp[0][m-1] << endl;
return 0;

}