zoj3190

/*
 * AC自动机，先对资源串和病毒串构成的字符串集合建立AC自动机，然后在trie树上做BFS求出在安全图上每个资源串
 * 到其他资源的最短路径，最后做一遍状态压缩dp即可
 */
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int N=10*1005+50005; //节点个数的最大值
const int S=2; //不同的字符 个数
const int NUM=10;
const int INF=0X7FFFFFFF;

struct node{
	node *sons[S], *fail;
	int d; //d为-1表示既不是病毒也不是资源的串，为-2表示病毒串，大于等于0表示资源串，并表示为资源的id
}nodes[N], *root;
int cnt;  //cnt是树中节点的 个数
node *que[N];
int n, m;
node *ns[NUM];
int dis[NUM][NUM], lens[NUM];
int mark[N], d[N];
int dp[NUM][1<<NUM];
void clear(){
	cnt=0;
	root=NULL;
}
node* newNode(){
	node* ans=&nodes[cnt++];
	memset(ans->sons, 0, S*sizeof(node*));
	ans->fail=NULL;
	ans->d=-1;
	return ans;
}
int hash(char ch){ //字符的哈希函数，根据不同的需要而定
	return ch-'0';
}
int id(node*& t){ //计算该节点的id
	return t-nodes;
}
//j表示当前关键字的标号
node* insert(node*& root, char* str, int d){
	node* t=root;
	int i, k;
	for(i=0; str[i]; i++){
		if(t->sons[k=hash(str[i])]==NULL){
			t->sons[k] = newNode();
		}
		t=t->sons[k];
	}
	t->d=d;
	return t;
}
void getFail(node*& root){
	int l, r, i;
	node *t;
	l=r=0;
	root->fail=root; //这样可以保证每个节点的fail指针都是非空的
	for(que[r++]=root; l!=r; ){
		t=que[l++];
		for(i=0; i<S; i++){
			if(t->sons[i]){
				que[r++]=t->sons[i];
				if(t==root){
					t->sons[i]->fail=t;
				}else{
					t->sons[i]->fail=t->fail->sons[i];
				}
			}else{ //增设虚拟节点
				if(t==root) t->sons[i]=t;
				else t->sons[i]=t->fail->sons[i];
			}
		}
	}
}
bool input(){
	scanf("%d%d", &n, &m);
	if(n==0 && m==0) return false;
	char str[1005];
	int i;
	clear();
	root=newNode();
	for(i=0; i<n; i++){
		scanf("%s", str);
		lens[i]=strlen(str);
		ns[i]=insert(root, str, i);
	}
	for(i=0; i<m; i++){
		scanf("%s", str);
		insert(root, str, -2);
	}
	return true;
}
void BFS(int s){
	int l, r, j;
	node *u, *v;
	l=r=0;
	for(que[r++]=&nodes[s], mark[s]=s, d[s]=0; l!=r; ){
		u=que[l++];
		for(j=0; j<S; j++){
			v=nodes[id(u)].sons[j];
			if(v->d==-2) continue;
			if(mark[id(v)]!=s){
				mark[id(v)]=s;
				d[id(v)]=d[id(u)]+1;
				que[r++]=v;
			}
		}
	}
}
void solve(){
	getFail(root);
	int i, j, k, tmp;
	for(i=0; i<n; i++){
		for(j=0; j<n; j++){
			dis[i][j]=(i==j ? 0:  INF);
		}
	}
	for(i=0; i<cnt; i++){
		mark[i]=-1;
	}
	for(i=0; i<n; i++){
		BFS(id(ns[i]));
		for(j=0; j<n; j++){
			if(mark[id(ns[j])]!=id(ns[i])) continue;
			if(dis[i][j]>d[id(ns[j])]){
				dis[i][j]=d[id(ns[j])];
			}
		}
	}
	int sum=1<<n;
	for(i=0; i<n; i++){
		for(j=0; j<sum; j++){
			dp[i][j]=INF;
		}
		dp[i][1<<i]=lens[i];
	}
	for(j=1; j<sum; j++){
		for(i=0; i<n; i++){
			if(!(j&(1<<i)) || dp[i][j]==INF) continue;
			for(k=0; k<n; k++){
				if(j&(1<<k) || dis[i][k]==INF) continue;
				tmp=dp[i][j]+dis[i][k];
				if(dp[k][j|(1<<k)] > tmp){
					dp[k][j|(1<<k)] = tmp;
				}
			}
		}
	}
	int ans=INF;
	for(i=0; i<n; i++){
		if(ans>dp[i][sum-1]){
			ans=dp[i][sum-1];
		}
	}
	printf("%d\n", ans);
}
int main(){
	//freopen("in.txt", "r", stdin);
	while(input()) solve();
	return 0;
}