题目描述

带有子串包含约束的最长公共子序列问题可以具体表述如下。

给定 $2$ 个长度分别为 $n$ 和 $m$ 的序列 $X$ 和 $Y$，以及一个子串包含约束集 $S$。

$S$ 中共有 $k$ 个字符串 $S=\{S_1,S_2,…,S_k\}$，其中字符串 $S_i$ 的长度为 $l_i$，$1\le i\le k$。带有子串包含约束的最长公共子序列问题就是要找出 $X$ 和 $Y$ 的包含约束集 $S$ 中所有字符串为其子串的最长公共子序列。

例如，如果给定的序列 $X$ 和 $Y$ 分别为 $X =\texttt{ actaagacct}$, $Y = \texttt{gacctacctc}$，子串包含约束集 $S=\{\texttt{ata}, \texttt{tact}\}$，则子序列 $\texttt{actacct}$ 是 $X$ 和 $Y$ 的一个无约束的最长公共子序列，而包含约束集 $S$ 中所有字符串为其子串的一个最长公共子序列是 $\texttt{atact}$ 。 在本题中请特别关注子串与子序列的区别。字符串 $T=t_1…t_n$ 的子串是一个形如 $T'=t_1+i…t_m+i$ 的字符串，其中，$0\le i$，$m + i\le n$。例如，$T =\texttt{ abcdefg}$，则 $\texttt{bcd}$ 是 $T$ 的一个子串，而 $\texttt{bce}$ 是 $T$ 的一个子序列，但不是 $T$ 的子串。

设计一个算法，找出给定序列 $X$ 和 $Y$ 带有子串包含约束 $S$ 的最长公共子序列。

输入格式

第 $1$ 行中给出正整数 $n,m,k$，$n$ 和 $m$ 分别表示给定序列 $X$ 和 $Y$ 的长度。$k$ 表示子串包含约束集 $S$ 中共有 $k$ 个字符串。

第 $2$ 行中有 $k$ 个整数 $l_i$，分别表示子串包含约束集 $S$ 中 $k$ 个字符串的长度。

第 $3$ 行和第 $4$ 行分别给出序列 $X$ 和 $Y$ 。

接下来 $k$ 行每行一个字符串 $S_i$。

输出格式

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

10 10 2
3 4
actaagacct
gacctacctc
ata
tact

5

提示

$m<300$，$n<300$，$k<6$，$0\le l_i\le 300$，$1\le i\le k$。

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