题目大意：

用集合A中的串构造出一个串，使之让很多其它的setB中的串成为他的子串。

思路分析：

和 Codeforces 86C 几乎相同。

只是这里是要用A中的构造。

先用A 和 B的串构造一个自己主动机。然后对于A集合的尾结点给出一个最大后缀匹配，对于B集合的尾结点给一个权值。

dp[i][j][k] 表示已经构造出来了一个长度为i的串，如今走到了自己主动机的j结点。i长度后面有k个字符是没有匹配到的。

继续在自己主动机上走进行状态转移。

if(isword >= k +1 )dp [i+1] [j->next[d] ][0] = max(dp [i+1] [ j->next[d] ][0] , dp[i][j][k] + j->next[d]->val)...

else if( k+1 <= 10) dp [i+1] [j->next[d] ] [k+1 ] = max (dp[i+1][ j->next[d] ] [k+1] , dp [i][j][k] + j->next[d]->val)

...

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <utility>

#include <string>

#include <vector>

#define inf 0x3f3f3f3f

using namespace std;

const int mod = 1000000009;

const char tab = 'a';

const int max_next = 26;

int rev[256];

struct trie

{

    struct trie *fail;

    struct trie *next[max_next];

    int isword,tip;

    int index;

};

struct AC

{

    trie *que[100005],*root,ac[100005];

    int head,tail;

    int idx;

    trie *New()

    {

        trie *temp=&ac[idx];

        for(int i=0;i<max_next;i++)temp->next[i]=NULL;

        temp->fail=NULL;

        temp->isword=0;

        temp->index=idx++;

        temp->tip=0;

        return temp;

    }

    void init()

    {

        idx=0;

        root=New();

    }

    void Insert(trie *root,char *word,int len,int cmd){

        trie *t=root;

        for(int i=0;i<len;i++){

            if(t->next[word[i]-tab]==NULL)

                t->next[word[i]-tab]=New();

            t=t->next[word[i]-tab];

        }

        if(cmd)t->isword=len;

        else t->tip++;

    }

    void acbuild(trie *root){

        int head=0,tail=0;

        que[tail++]=root;

        root->fail=NULL;

        while(head<tail){

            trie *temp=que[head++],*p;

            for(int i=0;i<max_next;i++){

                 if(temp->next[i]){

                    if(temp==root)temp->next[i]->fail=root;

                    else {

                        p=temp->fail;

                        while(p!=NULL){

                            if(p->next[i]){

                                temp->next[i]->fail=p->next[i];

                                break;

                            }

                            p=p->fail;

                        }

                        if(p==NULL)temp->next[i]->fail=root;

                    }

                    //if(temp->next[i]->fail->isword)

                    temp->next[i]->isword=max(temp->next[i]->isword,temp->next[i]->fail->isword);

                    temp->next[i]->tip+=temp->next[i]->fail->tip;

                    que[tail++]=temp->next[i];

                 }

                 else if(temp==root)temp->next[i]=root;

                 else temp->next[i]=temp->fail->next[i];

            }

        }

    }

    void tra()

    {

        for(int i=0;i<idx;i++)

        {

            if(ac[i].fail!=NULL)printf("fail = %d ",ac[i].fail->index);

            for(int k=0;k<max_next;k++)

                printf("%d ",ac[i].next[k]->index);

            puts("");

        }

    }

}sa;

char word[55];

int dp[65][1005][11];

int solve(int L)

{

    memset(dp,-1,sizeof dp);

    dp[0][0][0]=0;

    for(int i=0;i<L;i++)

    {

        for(int j=0;j<sa.idx;j++)

        {

            for(int k=0;k<10;k++)

            {

                if(dp[i][j][k]<0)continue;

                for(int d=0;d<4;d++)

                {

                    if(sa.ac[j].next[d]->isword>=k+1)

                        dp[i+1][sa.ac[j].next[d]->index][0]=max(dp[i+1][sa.ac[j].next[d]->index][0],dp[i][j][k]+sa.ac[j].next[d]->tip);

                    else if(k+1<=10)

                        dp[i+1][sa.ac[j].next[d]->index][k+1]=max(dp[i+1][sa.ac[j].next[d]->index][k+1],dp[i][j][k]+sa.ac[j].next[d]->tip);

                }

            }

        }

    }

    int ans=0;

    for(int l=1;l<=L;l++)

    for(int i=0;i<sa.idx;i++)

    ans=max(ans,dp[l][i][0]);

    return ans;

}

int main()

{

    rev['A']=0;

    rev['C']=1;

    rev['G']=2;

    rev['T']=3;

    int m,L,n;

    while(cin>>m>>n>>L)

    {

        sa.init();

        for(int i=1;i<=m;i++)

        {

            cin>>word;

            sa.Insert(sa.root,word,strlen(word),1);

        }

        for(int i=1;i<=n;i++)

        {

            cin>>word;

            sa.Insert(sa.root,word,strlen(word),0);

        }

        sa.acbuild(sa.root);

        printf("%d\n",solve(L));

    }

    return 0;

}