ZOJ Problem Set - 3535
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".
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 one line for each case. That is the maximum score you can get.
2 1 6 ab bc abc 1 1 3 b bb
Author: CHEN, Weijie
Contest: ZOJ Monthly, September 2011