#include <bits/stdc++.h>   using namespace std;   const int N = 105;   int M127;   string s;   int S, k, n;   int e[N][N];   int f[N][N][N];   int conv(char c) { return c -  a  + 1; }   int main() {     cin >> s;     S = s.size();     s =     + s;     memset(f, -127, sizeof(f));     M127 = f[0][0][0];     k = ({       long long first = 0;       int c = getchar(), n = 0;       for (; !isdigit(c); c = getchar()) n = (c ==  - );       for (; isdigit(c); c = getchar()) first = first * 10 + c -  0 ;       n ? -first : first;     });     n = ({       long long first = 0;       int c = getchar(), n = 0;       for (; !isdigit(c); c = getchar()) n = (c ==  - );       for (; isdigit(c); c = getchar()) first = first * 10 + c -  0 ;       n ? -first : first;     });     for (int i(1); i <= n; i++)       e[conv(({         char c = getchar();         while (c ==     || c ==   n ) c = getchar();         c;       }))][conv(({         char c = getchar();         while (c ==     || c ==   n ) c = getchar();         c;       }))] = ({         long long first = 0;         int c = getchar(), n = 0;         for (; !isdigit(c); c = getchar()) n = (c ==  - );         for (; isdigit(c); c = getchar()) first = first * 10 + c -  0 ;         n ? -first : first;       });     for (int i(1); i <= 26; i++) f[1][i][i != conv(s[1])] = 0;     for (int i(2); i <= S; i++)       for (int j(1); j <= 26; j++)         for (int kk(0); kk <= k; kk++) {           int ok = j != conv(s[i]);           if (kk < ok) continue;           for (int j2(1); j2 <= 26; j2++)             if (f[i - 1][j2][kk - ok] != M127)               f[i][j][kk] = max(f[i - 1][j2][kk - ok] + e[j2][j], f[i][j][kk]);         }     int res = M127;     for (int j(1); j <= 26; j++)       for (int kk(0); kk <= k; kk++) res = max(res, f[S][j][kk]);     cout << res;   }   