Vasya plays the LionAge II. He was bored of playing with a stupid computer, so he installed this popular MMORPG, to fight with his friends. Vasya came up with the name of his character — non-empty string s, consisting of a lowercase Latin letters. However, in order not to put up a front of friends, Vasya has decided to change no more than k letters of the character name so that the new name sounded as good as possible. Euphony of the line is defined as follows: for each pair of adjacent letters x and y (x immediately precedes y) the bonus c(x, y) is added to the result. Your task is to determine what the greatest Euphony can be obtained by changing at most k letters in the name of the Vasya's character.

Input

The first line contains character's name s and an integer number k (0 ≤ k ≤ 100). The length of the nonempty string s does not exceed 100. The second line contains an integer number n (0 ≤ n ≤ 676) — amount of pairs of letters, giving bonus to the euphony. The next n lines contain description of these pairs «x y c», which means that sequence xy gives bonus c (x, y — lowercase Latin letters,  - 1000 ≤ c ≤ 1000). It is guaranteed that no pair x y mentioned twice in the input data.

Output

Output the only number — maximum possible euphony оf the new character's name.

Examples

Input

winner 4
4
s e 7
o s 8
l o 13
o o 8


Output

36

Input

abcdef 1
5
a b -10
b c 5
c d 5
d e 5
e f 5


Output

20

Note

In the first example the most euphony name will be looser. It is easy to calculate that its euphony is 36.
import javax.swing.plaf.synth.SynthTextAreaUI;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class  C73{

    static BufferedReader br;
    static  long mod  = 998244353;
    //static TreeSet<Integer> pl  = new TreeSet<>();


    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        int tc = 1;
        boolean[] prime = new boolean[100000+5];
        // tc = cinI();
        //sieveOfEratosthenes(100000+1,prime);
        //System.out.println(pl);
        long mod  = (long) (1e9+7);
        while (tc-- > 0) {

            String[] ar = cinA();
            char[] x=ar[0].toCharArray();
            int k =getI(ar[1]);
            int[][] cost= new int[26][26];
            int n =cinI();

            for(int i=0;i<n;i++){
                String[] uv= cinA();
                int u =uv[0].charAt(0)-'a';
                int v =uv[1].charAt(0)-'a';
                cost[u][v]=getI(uv[2]);
             //   System.out.println(cost[u][v]);
            }
            int[][][] dp = new int[x.length][k+1][26];
            for(int i=0;i<x.length;i++){

          // System.out.println(i +" "+(x[i]-'a'));

                for(int j=0;j<=k;j++ ){

                    for(int c=0;c<26;c++){
                        dp[i][j][c]=Integer.MIN_VALUE/2;
                        if(i==0){
                            if(j>0 || c==x[i]-'a'){
                                dp[i][j][c]=0;
                                continue;
                            }
                        }

                        for(int r =0;r<26;r++){
                            if (c == x[i] - 'a') {

                                dp[i][j][c]=Math.max(dp[i][j][c],dp[i-1][j][r]+cost[r][c]);
                            }
                            else {
                                if(j>0)
                                dp[i][j][c] = Math.max(dp[i - 1][j - 1][r] + cost[r][c], dp[i][j][c]);
                            }
                        }
                    }

                }
            }
            int max=dp[x.length-1][0][x[x.length-1]-'a'];
            for(int i=1;i<=k;i++){
                for(int j=0;j<26;j++){

                    max=max(dp[x.length-1][i][j],max);
                    //System.out.println(i+" "+j+" "+dp[x.length-1][i][j]);
                }// a b c d e f g h i j k l m n o p q r s t u v w x y z
            }
            System.out.println(max);





        }


    }
    public static void dfs(HashSet<Integer>[] gg,int node,boolean[] vis,int compI,int str,int[] min,int[] comp,int[] cost){

        HashSet<Integer> c  = gg[node];
        str+=1;
        min[compI]=min(min[compI],cost[node]);
        vis[node]=true;
        for(int ch:c){
            if(vis[ch]==false){
                dfs(gg,ch,vis,compI,str,min,comp,cost);
            }
        }
        comp[compI]=str;
    }


























    private static long calP(HashMap<Integer, HashSet<Integer>> graph, boolean[] vis, Stack<Integer> list,
                             long[] cost, long[] dp) {
        int par = list.pop();
        HashSet<Integer> childs = graph.get(par);
        if(childs.size()==0){
            dp[par]=0;
            return dp[par];
        }
        vis[par]=true;
        for(int c: childs){
            if(vis[c]==false){
                list.add(c);
                calP(graph, vis, list, cost, dp);
            }
            if(cost[par]>cost[c]){
                dp[par]=max(dp[par], dp[c]+cost[par]-cost[c]);
            }

        }
        return dp[par];
    }

    public static int max(int[] max) {
        int maxS=0;
        int currSum=0;
        for(int i=0;i<max.length;i++){
            currSum= currSum+max[i];
            maxS=Math.max(maxS,currSum);
        }
        // System.out.println(maxS);
        return maxS;
    }


    public static boolean isSorted(int[] arr){

        for(int i=0;i<arr.length-1;i++){
            if(arr[i]>arr[i+1]){
                return false;
            }
        }
        return true;
    }



    private static long gcd(long a, long b) {
        if (a == 0)
            return b;
        if (b == 0)
            return a;

        // base case
        if (a == b)
            return a;

        // a is greater
        if (a > b)
            return gcd(a%b, b);
        return gcd(a, b%a);
    }


    public static long min(long a,long b) {
        return Math.min(a,b);
    }
    public static int min(int a,int b) {
        return Math.min(a,b);
    }























    static void sieveOfEratosthenes(int n,boolean[] prime)
    {
        // Create a boolean array
        // "prime[0..n]" and
        // initialize all entries
        // it as true. A value in
        // prime[i] will finally be
        // false if i is Not a
        // prime, else true.

        for (int i = 0; i <= 100000; i++)
            prime[i] = true;

        for (int p = 2; p * p <= 100000; p++)
        {
            // If prime[p] is not changed, then it is a
            // prime

            if (prime[p] == true)
            {
                // pl.add(p);  //  System.out.println(p);
                // Update all multiples of p
                for (int i = p * p; i <= 100000; i += p)
                    prime[i] = false;
            }
        }


    }











    public  static  int[] readArray(int n,int x ,int z)throws Exception{
        int[] arr= new int[n];
        String[] ar= cinA();
        for(int i =x ;i<n+x;i++){
            arr[i]=getI(ar[i-x]);
        }
        return arr;
    }
    public  static  long[] readArray(int n,int x )throws Exception{
        long[] arr= new long[n+x];
        String[] ar= cinA();
        for(int i =x ;i<n+x;i++){
            arr[i]=getL(ar[i-x]);
        }
        return arr;
    }

    public static void arrinit(String[] a,long[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Long.parseLong(a[i]);
        }
    }
    public  static HashSet<Integer>[]  Graph(int n,int edge,int directed)throws Exception{
        HashSet<Integer>[] tree=  new HashSet[n];

        for(int j=0;j<edge;j++){

            String[] uv = cinA();
            int u = getI(uv[0]);
            int v = getI(uv[1]);
            if(directed==0){

                tree[v].add(u);
            }
            tree[u].add(v);
        }
        return tree;
    }
    public static void arrinit(String[] a,int[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Integer.parseInt(a[i]);
        }
    }


    static double findRoots(int a, int b, int c) {
        // If a is 0, then equation is not
        //quadratic, but linear


        int d = b * b - 4 * a * c;
        double sqrt_val = Math.sqrt(Math.abs(d));


        // System.out.println("Roots are real and different \n");

        return Math.max((double) (-b + sqrt_val) / (2 * a),
                (double) (-b - sqrt_val) / (2 * a));


    }

    public static String cin() throws Exception {
        return br.readLine();
    }

    public static String[] cinA() throws Exception {
        return br.readLine().split(" ");
    }
    public static String[] cinA(int x) throws Exception{
        return br.readLine().split("");
    }

    public static String ToString(Long x) {
        return Long.toBinaryString(x);
    }

    public static void cout(String s) {
        System.out.println(s);
    }

    public static Integer cinI() throws Exception {
        return Integer.parseInt(br.readLine());
    }

    public static int getI(String s) throws Exception {
        return Integer.parseInt(s);
    }

    public static long getL(String s) throws Exception {
        return Long.parseLong(s);
    }

    public static long max(long a, long b) {
        return Math.max(a, b);
    }
    public static int max(int a, int b) {
        return Math.max(a, b);
    }

    public static void coutI(int x) {
        System.out.println(String.valueOf(x));
    }

    public static void coutI(long x) {
        System.out.println(String.valueOf(x));
    }

    public static Long cinL() throws Exception {
        return Long.parseLong(br.readLine());
    }

    public static void arrInit(String[] arr, int[] arr1) throws Exception {
        for (int i = 0; i < arr.length; i++) {
            arr1[i] = getI(arr[i]);
        }

    }
}
