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

题目描述

带有子串包含约束的最长公共子序列问题可以具体表述如下。 给定2个长度分别为n和m的序列X和Y,以及一个子串包含约束集S。 S中共有k个字符串$S=\{S_1,S_2,…,S_k\}$,其中字符串$S_i$的长度为$l_i$,1≤i≤k。带有子串包含约束的最长公共子序列问题就是要找出X和Y的包含约束集S中所有字符串为其子串的最长公共子序列。 例如,如果给定的序列X和Y分别为X=actaagacct, Y=gacctacctc,子串包含约束集S={ata, tact},则子序列actacct是X和Y的一个无约束的最长公共子序列,而包含约束集S中所有字符串为其子串的一个最长公共子序列是atact 。 在本题中请特别关注子串与子序列的区别。字符串$T=t_1…t_n$的子串是一个形如$T$’$=t_1+i…t_m+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个整数$l_i$,$0≤l_i≤300,1≤i≤k$,分别表示子串包含约束集S中k个字符串的长度。 第3行和第4行分别给出序列X和Y 。 接下来k行每行一个字符串$S_i$

输出格式


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

输入输出样例

输入样例 #1

10 10 2
3 4
actaagacct
gacctacctc
ata
tact

输出样例 #1

5

说明

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