#include <iostream>
#include <stdio.h>
#define L_MAX 10
#define K_MAX 26
#define MIN(A, B) ((A) < (B) ? (A) : (B))
char buffer[L_MAX + 1];
int L, K;
int cost[K_MAX];
int DT[L_MAX + 1][L_MAX + 1];
int main() {
freopen("input.txt", "r", stdin);
int T; scanf("%d", &T); while (T--) {
scanf("%d %d", &L, &K);
scanf("%s", buffer);
for (int i = 0; i < K; i++) {
int c1, c2; scanf("%d %d", &c1, &c2);
cost[i] = MIN(c1, c2);
}
DT[0][L] = 0;
for (int i = 1; i <= L; i++) {
DT[i][L] = DT[i - 1][L] + cost[buffer[i - 1] - 'a'];
}
for (int i = L - 1; i >= 0; i--) {
DT[0][i] = DT[0][i + 1] + cost[buffer[i] - 'a'];
}
for (int i = 1; i < L; i++) {
for (int j = L - 1; j >= i; j--) {
DT[i][j] = MIN(DT[i - 1][j] + cost[buffer[i - 1] - 'a'],
DT[i][j + 1] + cost[buffer[j] - 'a']);
if (buffer[i - 1] == buffer[j]) {
DT[i][j] = MIN(DT[i][j], DT[i - 1][j + 1]);
}
}
}
int ans = DT[0][1];
for (int i = 0; i < L; i++) {
ans = MIN(ans, DT[i][i + 0]);
ans = MIN(ans, DT[i][i + 1]);
}
printf("%d\n", ans);
}
return 0;
}
댓글