#include<bits/stdc++.h>

#define llu unsigned long long
#define ll long long
#define pi 3.141592
#define nl printf("\n")
#define f(i,l1,l2) for(i=l1;i<l2;i++)
#define gc getchar_unlocked
#define vi vector<int>
#define vit vi::iterator
#define all(c) c.begin(), c.end()
#define pb push_back
#define endl "\n"
using namespace std;

/*void fin(int &x)       //does not compile in codeblocks but does in online judges
{                        //use if input too large ( only for integers )
int i=0;x=0;
register int c=gc();
while(c<48||c>57)
c=gc();
while(c>47&&c<58)
{
x=(x<<1)+(x<<3) + c-48;
i++;
c=gc();
}
}*/
int n,m;
int a[19];
int ab[19][19];
int dp[1<<18][18][19];
map<string,int> h;

int func(int mask, int i, int k)
{
    //cout<<i<<" "<<k<<endl;
    if(!mask)
        return 0;
    int ans = dp[mask][i][k];

    if(ans!=-1)
      return ans;

    int j;
    f(j,0,n)
    {
        if(mask&(1<<j))
        {
            if(ab[i][j]!=INT_MIN)
                {ans = max(ans, func(mask&(~(1<<j)),j,k+1) + (k)*a[j]);
                //cout<<ans<<" "<<k<<" "<<i<<" "<<endl;
                }
        }
    }
    return (dp[mask][i][k] = ans);
}

int main()
{
    //std::ios::sync_with_stdio(false);
    //cin.tie(0);
    int t,i,j,e;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        cin.ignore();
        f(i,0,n)
        {

            char rr[50];
            gets(rr);
            int len = strlen(rr);
            //cout<<a;
            int pos;
            for(int g=len-1; g>=0; g--)
            {
                if(rr[g]==' ')
                {
                    pos = g;
                    break;
                }
            }
            string s;
            for(int g=0; g<=pos-1; g++)
                s.pb(rr[g]);
            int y=0;
            for(int g=pos+1; g<len; g++)
            {
                y = y*10 + (rr[g]-'0');
            }
            h[s] = i;
            a[i] = y;
            //cout<<s<<":";
            //cout<<y<<endl;


        }
        map<string,int> :: iterator it;
        /*for(it= h.begin();it!=h.end();it++)
        {
            cout<<it->first<<" "<<it->second<<endl;
        }*/
        /*f(i,0,n)
            cout<<a[i]<<" ";
            cout<<endl;*/
        f(i,0,19)
            f(j,0,19)
                ab[i][j] = 0;

        f(i,0,m)
        {
            string s1,s2;
            // string x;
            // cin>>s1>>x>>s2;
            char rr[100];
            gets(rr);
            int len = strlen(rr);
            int hpos, apos;

            for(int g=0; g<len; g++)
            {
                if(rr[g]=='-')
                {
                    hpos = g;
                    break;
                }
            }
            for(int g=0; g<len; g++)
            {
                if(rr[g]=='>')
                {
                    apos = g;
                    break;
                }
            }

            for(int g=0; g<=hpos-2; g++)
            {
                s1.pb(rr[g]);

            }

            for(int g=apos+2; g<len; g++)
            {
                s2.pb(rr[g]);

            }


            // cout<<s1<<" "<<s2<<endl;
            ab[h[s1]][h[s2]] = 0;
            ab[h[s2]][h[s1]] = INT_MIN;
        }



        /*f(i,0,19)
            f(j,0,19)
                if(ab[i][j] != 0)
                    ab[i][j] = INT_MIN;
        */
        f(i,0,1<<n)
            f(j,0,n)
                for(int k=0;k<=n;k++)
                    dp[i][j][k] = -1;

        int mask;

        int ans = 0;
        f(mask,1,1<<n)
        {

            f(j,0,n)
            {
                //int k = 1;
                if(mask&(1<<j))
                {

                    //if(mask==7)
                    //  cout<<a[j]<<" "<<k<<(mask&(~(1<<j)))<<endl;
                    ans = max(ans, a[j] + func(mask&(~(1<<j)), j, 2));
                }
            }
        }

        /*f(i,0,1<<n)
        {
            f(j,0,n)
            cout<<dp[i][j]<<" ";
            cout<<endl;
        }*/


        cout<<ans<<endl;

    }

    return 0;
}