带有子串包含约束的最长公共子序列问题可以具体表述如下。
给定 $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=$ actaagacc， $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$ 的最长公共子序列的长度输出。
10 10 2 3 4 actaagacct gacctacctc ata tact
5
字符串仅包含大小写字母。
Comet OJ