#include<bits/stdc++.h>
using namespace std;
#define nl "\n"
#define cnl cout << nl;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned ll
#define RV return void
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define fixed(n) fixed << setprecision(n)
#define cin(v) for(auto&x:v) cin >> x;
#define cout(v) for(auto&x:v) cout << x << " ";
void files(){
    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif
}


int n  , m ;
string str , line , num;
vector < int > v;
map < string , int > mp;
vector < vector < int > > adj , dp;
vector < bool > vis;


void rec2(int node , int par){
    if(vis[node]) return;
    if(sz(adj[node])==0) return;

    vis[node]=1;

    for(auto& ch : adj[node]) {
        adj[par].pb(ch);
        rec2(ch , par);
    }
}


int rec(int day , int mask){
    if( !mask) return 0;

    int & ret = dp[day][mask];
    if(~ret)
        return ret;
    ret =0;
    for(int i =0 ; i < n ; i++){
        if((mask >> i) & 1){
            bool flag=0;
            for(auto & ch : adj[i]) {
                if((mask >> ch) & 1) {
                    flag=1;
                    break;
                }
            }
            if(flag) continue;

            ret = max(ret , day * v[i] + rec(day+1 , mask ^ (1 << i)));
        }
    }
    return ret;
}

void solve(){


    cin >> n >> m ;
    v.assign(n,0);
    mp.clear();
    adj.assign(n+1 , vector < int > ());
    cin.ignore();
    dp.assign(n+1 , vector < int > (1<<n , -1));
    for(int i =0 ; i < n ; i++){
        getline(cin, line);
        int idx = sz(line) -1 , id2=0;
        num="" , str="";

        while(idx >=0 and line[idx] !=' ') num += line[idx--];
        reverse(all(num));
        for(auto& c : num) v[i] = v[i] * 10 + (c-'0');

        while(id2 < idx) str += line[id2++];
        mp[str] = i;

        // cout << str << "\n" << v[i] << nl;
    }

   for(int i =0 ; i < m ; i++){
       getline(cin ,str);
       auto it = str.find(" --> ");
       string s1 = str.substr(0 , it );
       string s2 = str.substr(it+5);
       adj[mp[s2]].pb(mp[s1]);
   }

    for(int i =0 ; i < n ; i++){
        vis.assign(n+1,0);
        vis[i]=1;
        rec2(i , i);
    }

    cout << rec(1 , (1 << n) - 1) << nl;



}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    //  files();


    int testCase=1;
        cin >> testCase ;
        cin.ignore();
    for(int i=1 ; i <= testCase ; i++){
        solve();
    }

    return 0;
}