#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define inf 0x3f3f3f3f
const int M = 705;
int read()
{
    int x=0,flag=1;
    char c;
    while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*flag;
}
int n,m,cnt,ans,tot,S,T,f[M],dis[M];
int r[M],c[M];
char s[M][M];
queue<int> q;
set<string> p;
map<string,int> id;
struct edge
{
    int v,c,next;
    edge(int V=0,int C=0,int N=0) : v(V) , c(C) , next(N) {}
} e[M*M];
void add_edge(int u,int v,int c)
{
    printf("%d %d\n",u,v);
    e[++tot]=edge(v,c,f[u]),f[u]=tot;
    e[++tot]=edge(u,0,f[v]),f[v]=tot;
}
int bfs()
{
    memset(dis,0,sizeof dis);
    dis[S]=1;
    q.push(S);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=f[u]; i; i=e[i].next)
        {
            int v=e[i].v;
            if(e[i].c>0 && !dis[v])
            {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    if(!dis[T]) return 0;
    return 1;
}
int dfs(int u,int ept)
{
    if(u==T) return ept;
    int flow=0,tmp=0;
    for(int i=f[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(dis[u]+1==dis[v] && e[i].c)
        {
            tmp=dfs(v,min(e[i].c,ept));
            if(!tmp) continue;
            ept-=tmp;
            e[i].c-=tmp;
            e[i^1].c+=tmp;
            flow+=tmp;
            if(!ept) break;
        }
    }
    return flow;
}
void work(string s,int tp,int u)
{
    string a,b;
    int len=s.length();
    for(int i=0,r,flag; i<len; i=r+1)
    {
        r=i;
        if(s[i]=='_') continue;
        while(r+1<len && s[r+1]!='_') r++;
        a=s.substr(i,r-i+1);
        b=a;
        reverse(b.begin(),b.end());
        if(b<a) swap(a,b),flag=-1;
        else flag=1;
        if(a==b)
        {
            p.insert(a);
            continue;
        }
        if(!id.count(a))
        {
            id[a]=++cnt;
            id[b]=++cnt;
            add_edge(id[a],id[b],2);
        }
        flag*=tp;
        if(flag==1) add_edge(S,id[a],inf);
        else if(flag==-1) add_edge(id[b],T,inf);
        else add_edge(id[b],u,inf),add_edge(u,id[a],inf);
    }
}
void solve()
{
    p.clear();
    id.clear();
    n=read();
    m=read();
    cnt=n+m;
    for(int i=1; i<=n; i++) r[i]=read();
    for(int i=1; i<=m; i++) c[i]=read();
    for(int i=1; i<=n; i++) scanf("%s",s[i]+1);
    S=0;
    T=M-1;
    string tmp;
    for(int i=1; i<=n; i++)
    {
        tmp=s[i]+1;
        work(tmp,r[i],i);
    }
    for(int i=1; i<=m; i++)
    {
        tmp="";
        for(int j=1; j<=n; j++)
            tmp+=s[j][i];
        work(tmp,c[i],i+n);
    }
    while(bfs()) ans+=dfs(S,inf);
    printf("%d\n",ans+(int)(p.size()));
}
int main()
{
    int Cases=read();
    while(Cases--)
    {
        tot=1;
        ans=0;
        memset(f,0,sizeof f);
        solve();
    }
}