WA on test#4

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
int n, m;
string ss, s;
int del[maxn], add[maxn];
int f[maxn][maxn];
int main() {
	cin >> n >> m;
	cin >> ss;
	s = "", s += "%", s += ss;
	for (int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		cin >> add[c] >> del[c];
	}
	memset(f, 0x3f, sizeof(f));
	for (int i = 1; i <= m; i++) {
		f[i][i] = 0;
	}
	for (int j = 1; j <= m; j++) {
		for (int i = j - 1; i >= 1; i--) {
			if (s[i] == s[j]) {
				f[i][j] = f[i + 1][j - 1];
			} else {
				f[i][j] = min(f[i + 1][j] + min(add[s[i]], del[s[i]]), f[i][j - 1] + min(add[s[j]], del[s[j]]));
			}
		}
	}
	cout << f[1][m] << endl;
	return 0;
}