import java.io.*;
import java.util.HashMap;
public class Main{

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		HashMap<String,Integer> hm = new HashMap<String,Integer>();
		
		String[] NM = br.readLine().split("\\s");
		int N = Integer.parseInt(NM[0]);
		int M = Integer.parseInt(NM[1]);
		
		String str = br.readLine();
		String s[] = new String[M];
		for(int i = 0; i < M; i ++){
			s[i] = str.substring(i, i+1);
		}
		
		for(int i = 0; i < N; i ++){
			String temp[] = br.readLine().split("\\s");
			String alp = temp[0];
			int cost = Math.min(Integer.parseInt(temp[1]), Integer.parseInt(temp[2]));
			hm.put(alp, cost);
		}
		
		int dp[][] = new int[M][M];
		
		for(int i = M-2; i >= 0; i--){
			for(int j = i+1; j < M; j ++){
				if(s[i].equals(s[j])){
					dp[i][j] = dp[i+1][j-1];
				}else{
					dp[i][j] = Math.min(dp[i+1][j] + hm.get(s[i]), dp[i][j-1] + hm.get(s[j]));
				}
			}
		}
//		for(int i = 0; i < M;i++){
//			for(int j = 0; j < M;j++){
//				System.out.print(dp[i][j]+"	");
//			}System.out.println();
//		}
		System.out.println(dp[0][M-1]);
	}
}