#4136. [FJOI2015]带子串包含约束LCS问题

内存限制:256 MiB 时间限制:30 Sec

题目描述

带有子串包含约束的最长公共子序列问题可以具体表述如下。 
给定2个长度分别为n和m的序列X和Y,以及一个子串包含约束集S。
S中共有k个字符串S={S1,S2,…,Sk},其中字符串Si的长度为li,1≤i≤k。带有子串包含约束的最长公共子序列问题就是要找出X和Y的包含约束集S中所有字符串为其子串的最长公共子序列。 
例如,如果给定的序列X和Y分别为X=actaagacct, Y=gacctacctc,子串包含约束集S={ata, tact},则子序列actacct是X和Y的一个无约束的最长公共子序列,而包含约束集S中所有字符串为其子串的一个最长公共子序列是atact 。 
在本题中请特别关注子串与子序列的区别。字符串T=t1…tn的子串是一个形如T’=t1+i…tm+i的字符串,其中,0≤i,m+i≤n。例如,T=abcdefg,则bcd是T 的一个子串,而bce是T的一个子序列,但不是T 的子串。
设计一个算法,找出给定序列X和Y带有子串包含约束S的最长公共子序列。 

输入格式

第1行中给出正整数n,m,k,m<300, n<300, k<6。n和m分别表示给定序列X和Y的长度。k表示子串包含约束集S中共有k个字符串。
第2行中有k个整数li,0≤li≤300,1≤i≤k,分别表示子串包含约束集S中k个字符串的长度度。
第3行和第4行分别给出序列X和Y 。
接下来k行每行一个字符串Si

输出格式

将计算出的X和Y带子串包含约束S的最长公共子序列的长度输出。

样例

样例输入


			
10 10 2
3 4
actaagacct
gacctacctc
ata
tact

样例输出


			
5

数据范围与提示

字符串仅包含大小写字母.


2016.3.26加强数据 By immortalCO