Paul Erdős 的预言成真了。终于,一股外星力量登陆了地球。与我们的预期相反,他们没有要求人类计算拉姆齐数的值(也许他们自己已经解决了)。他们提出了另一个问题,这个问题看起来就像计算拉姆齐数一样困难。外星人威胁说,如果人类不在两个小时内解决这个问题,他们将毁灭地球。
在讲述问题之前,他们介绍了超字符串的概念。超字符串是由一些基本字符串串联而成的。假设给你一个基本字符串列表 b1, b2, ..., bn。现在,由索引列表 i1, i2, ..., im 组成的超字符串是基本字符串 bi1, bi2, ..., bim 的串联。超字符串可能非常大,并且对计算机来说对其进行操作的成本非常高。
外星人要求人类计算超字符串 t 与字符串 s 的最长公共子序列的长度。
输入
输入的第一行包含单个整数 n (1 ≤ n ≤ 2000) — 基本字符串的数量。
接下来的 n 行包含基本字符串的值。每个基本字符串均由小写拉丁字母组成。一个基本字符串不能为空字符串,并且所有n个基本字符串的长度之和不超过106。
下一行包含单个整数 m (1 ≤ m ≤ 2000) — 给定超字符串 t 中基本字符串的数量。
下一行包含 m 个空格分隔的整数 i1, i2, ..., im (1 ≤ ij ≤ n) — 超字符串 t 中基本字符串的索引。
最后一行包含一个非空字符串 s。字符串s由小写拉丁字母组成,长度不超过2000个字符。
输出
打印超字符串 t 和字符串 s 的最长公共子序列的长度。如果没有公共子序列则打印0。
示例
输入 #1
2 cba dgh 2 1 2 aedfhr
输出 #1
3
输入 #2
2 b a 5 1 2 1 2 1 aaa
输出 #2
2
注意
字符串 s 的长度是其中的字符数。如果将字符串s的长度标记为|s|,则字符串s可以表示为s = s1s2...s|s|。
非空字符串 y = s[p1p2... p|y|] = sp1sp2... sp|y| (1 ≤ p1 < p2 < ... < p|y| ≤ |s|) 是字符串 s 的子序列。例如,“coders”是“codeforces”的子序列。