#include<iostream>#include<algorithm>#include<string>#include<cstdio>#include<string>#include<cstring>#include<cmath>using namespace std;char str[202][10002],sn[202][22];int next[22];void Getnext(char *T,int next[]){ int j=0,k=-1; next[0]=-1; while(j<(int)strlen(T)){ if(k==-1||T[j]==T[k]){ j++;k++; next[j]=k; } else k=next[k]; }}int Kmp(char *a,char *b,int &k){ int ans=0,i=0,j=0,alen,blen; alen=strlen(a); blen=strlen(b); for(i=0;i<alen;i++){ while(j>0&&a[i]!=b[j])j=next[j]; if(a[i]==b[j])++j; if(j==blen){ if(ans==0) k=i-blen+2; ans++; j=next[j]; } } return ans;}inline int MIN(int a,int b){return a<b?a:b;}inline int max(int a,int b){return a>b?a:b;}const int INF = 100000000;#define MAX 250int match[MAX];bool sx[MAX],sy[MAX];int lx[MAX],ly[MAX],map[MAX][MAX];bool path(int u,int n){ sx[u]=true; for(int v=0;v<n;v++) if(!sy[v]&&lx[u]+ly[v]==map[u][v]) { sy[v]=true; if(match[v]==-1||path(match[v],n)) { match[v]=u; return true; } } return false;}int KM(int n){ int i,j; for(i=0;i<n;i++) { lx[i]=-INF; ly[i]=0; for(j=0;j<n;j++) if(lx[i]<map[i][j]) lx[i]=map[i][j]; } memset(match,-1,sizeof(match)); for(int u=0;u<n;u++) while(1) { memset(sx,0,sizeof(sx)); memset(sy,0,sizeof(sy)); if(path(u,n)) break; int dmin=INF; for(i=0;i<n;i++) if(sx[i]) for(j=0;j<n;j++) if(!sy[j]) dmin=MIN(lx[i]+ly[j]-map[i][j],dmin); for(i=0;i<n;i++) { if(sx[i]) lx[i]-=dmin; if(sy[i]) ly[i]+=dmin; } } int sum=0; for(j=0;j<n;j++) sum+=map[match[j]][j]; return sum;}int main(){ int n,m,i,j,len; while(cin>>m>>n){ for(i=0;i<n+m;i++){ cin>>sn[i]; getchar(); len=strlen(sn[i]); sn[i][len-1]=' '; gets(str[i]); } int k,num=0; memset(map,0,sizeof(map)); for(i=0;i<m;i++){ for(j=m;j<m+n;j++){ Getnext(sn[j],next); num=Kmp(str[i],sn[j],k); if(num){ map[i][j-m]=num*k; } } } for(i=m;i<m+n;i++){ for(j=0;j<m;j++){ Getnext(sn[j],next); num=Kmp(str[i],sn[j],k); if(num){ map[j][i-m]+=num*k; } } } n=max(m,n); printf("%dn",KM(n)); } return 0;}
