#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <queue>#include <iostream>#include <vector>using namespace std;const int N = 55;const int M = 55 * 20;const int S = 26;int q[M], word[M], son[M][S], fail[M];int pp;int dp[N][M][N];vector <pair <int, int> > extend[N];void init(){ pp = 1; word[0] = 0; memset(son[0], 0, sizeof (son[0])); memset(dp, -1, sizeof (dp));}void insert(char * str){ int u = 0; for (int i = 0; str[i]; i++) { int idx = str[i] - 'a'; if (!son[u][idx]) { word[pp] = 0; memset(son[pp], 0, sizeof (son[pp])); son[u][idx] = pp++; } u = son[u][idx]; } word[u] += 1;}void build(){ int head = 0, tail = 0; for (int i = 0; i < S; i++) { if (son[0][i]) { q[tail++] = son[0][i]; fail[son[0][i]] = 0; } } while (head != tail) { int u = q[head++]; for (int i = 0; i < S; i++) { int v = son[u][i]; if (v) { q[tail++] = v; fail[v] = son[fail[u]][i]; word[v] += word[fail[v]]; } else son[u][i] = son[fail[u]][i]; } }}char A[N][16], B[N][16];int alen[N];bool isok(int aidx, int bidx, int len){ for (int i = alen[aidx] - len, j = 0; j < len; i++, j++) { if (A[aidx][i] != A[bidx][j]) return false; } return true;}void strinit(int num){ extend[0].clear(); for (int i = 1; i <= num; i++) { extend[0].push_back(make_pair(i, 0)); } for (int i = 1; i <= num; i++) { extend[i].clear(); for (int j = 1; j <= num; j++) { int maxlen = min(alen[i], alen[j]); for (int k = 0; k <= maxlen; k++) { if (isok(i, j, k)) extend[i].push_back(make_pair(j, k)); } } }}void doextend(int aidx, int asta, int &dnum, int sta, int & end){ int u = sta; for (int i = asta; i < alen[aidx]; i++) { u = son[u][A[aidx][i] - 'a']; dnum += word[u]; } end = u;}int main(){ int m, n, L; while (scanf("%d %d %d", &m, &n, &L) == 3) { init(); for (int i = 1; i <= m; i++) { scanf("%s", A[i]); alen[i] = strlen(A[i]); } for (int i = 1; i <= n; i++) { scanf("%s", B[i]); insert(B[i]); } strinit(m); build(); int ans = 0; dp[0][0][0] = 0; for (int i = 0; i <= L; i++) { for (int j = 0; j < pp; j++) { for (int k = 0; k <= m; k++) { if (dp[i][j][k] == -1) continue; for (int l = 0; l < (int) extend[k].size(); l++) { int nxtk = extend[k][l].first, nxtj = -1, len = extend[k][l].second, dnum = 0; int dl = alen[nxtk] - len; if (i + dl > L) continue; doextend(nxtk, len, dnum, j, nxtj); dp[i + dl][nxtj][nxtk] = max(dp[i + dl][nxtj][nxtk], dp[i][j][k] + dnum); ans = max(ans, dp[i + dl][nxtj][nxtk]); } } } } printf("%dn", ans); } return 0;}
