Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
109 - ZOJ Monthly, September 2011 - G
Gao the String II

Time Limit: 1 Second      Memory Limit: 65536 KB

Somebody wants to gao the string again!

In this turn, he defines a new operation link. This operation can link two strings into one. Further more, this operation can suffer overlap between prefix and suffix. For example, we can link "abc" and "bcd" into "abcd". Of course, "abc" and "bcd" can also be linked into "abcbcd". Here comes a game with this operation. In this game, I will give you two sets of strings(set A and set B) and an integer L. You have an empty string S at the beginning. You can link several times. Each time, you can link S and a string in set A into a new string S'. After that, the string S' will replace the string S. Finally, you will get a string S(0 ≤ |S|L). The score you get is the sum of Fi. Fi is the amount of matching place of the i-th string in B in S.

Notice that you can't link a string in set A and S. For example, you can't get "abaaca" when S="aca" and another string s="aba".

Input

There are multiple test cases. The first line of each case contains three integer m n L( 1 ≤ m,n,L ≤ 50 ). Then following m+n lines, each line contains a string only with lowercase letter (the length of each string will not exceed 10). The first m lines describe set A. The last n lines describe set B. Process to the end of file.

Output

Output one line for each case. That is the maximum score you can get.

Sample Input

2 1 6
ab
bc
abc
1 1 3
b
bb

Sample Output

2
2

Author: CHEN, Weijie
Submit    Status