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 java.io.*;
import java.util.*;

public class CodeForces {
    public static void main(String[] args) {
        FastIO io = FastIO.create();

        String start = io.nextToken();
        int k = io.nextInt();
        int n = io.nextInt();

        Map<String, Integer> bonus = new HashMap<>();

        for(int i = 0; i < n; i++) {
            String f = io.nextToken();
            String s = io.nextToken();

            int value = io.nextInt();

            bonus.put(f + s, value);
        }

        int[][] previous = new int['z' - 'a' + 1][k + 1];
        for (int[] row : previous) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }

        Arrays.fill(previous[start.charAt(0) - 'a'], 0);

        if (k > 0) {
            for (int[] row : previous) {
                for (int i = 0; i < k; i++) {
                    row[i] = 0;
                }
            }
        }

        for(int i = 1; i < start.length(); i++) {
            int[][] next = new int['z' - 'a' + 1][k + 1];
            for (int[] row : next) {
                Arrays.fill(row, Integer.MIN_VALUE);
            }

            for(char first = 'a'; first <= 'z'; first++) {
                for (char second = 'a'; second <= 'z'; second++) {
                    String s = "" + first + second;
                    int price = second == start.charAt(i) ? 0 : 1;

                    int gain = bonus.getOrDefault(s, 0);

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

                        int current = next[second - 'a'][j - price];

                        if (previous[first - 'a'][j] != Integer.MIN_VALUE) {
                            int newValue = previous[first - 'a'][j] + gain;

                            if (newValue > current) {
                                next[second - 'a'][j - price] = newValue;
                            }
                        }
                    }
                }
            }
            previous = next;
        }


        int max = Integer.MIN_VALUE;
        for (int[] row : previous) {
            for (int e : row) {
                max = Math.max(max, e);
            }
        }

        io.println(max);

        io.close();
    }

    static class FastIO extends PrintWriter {
        BufferedReader br;
        StringTokenizer st;

        public FastIO(InputStream is, OutputStream os) {
            super(new BufferedOutputStream(os));
            br = new BufferedReader(new InputStreamReader(is));
        }

        public static FastIO create() {
            return new FastIO(System.in, System.out);
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return "";
        }
    }
}