D. Гипер Строка
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Предсказание Пола Эрдеша сбылось. Инопланетные захватчики приземлились на Землю. Правда, не смотря на наши ожидания, они не спросили значение числа Рамсея (может быть, они посчитали его сами). Пришельцы попросили решить другую задачу, которая на вид ничуть не проще чисел Рамсея. Они грозились, что если люди не сумеют решить поставленную задачу за 2 часа, Земле не поздоровится.

Перед тем как рассказать задачу, пришельцы определили понятие Гипер Строки. Гипер Строка — это строка, составленная из нескольких базовых строк. Пусть у нас имеется список базовых строк b1, b2, ..., bn. Гипер Строкой, составленной из индексов i1, i2, ..., im, называется конкатенация базовых строк bi1, bi2, ..., bim. Гипер Строки могут получаться очень длинными, поэтому любые операции с ними выполняются достаточно долго.

Пришельцы попросили людей посчитать длину наидлиннейшей общей подпоcледовательности Гипер Строки t и строки s. Ваша задача — помочь человечеству.

Входные данные

Первая строка входных данных содержит единственное целое число n (1 ≤ n ≤ 2000) — количество базовых строк.

Следующие n строк содержат базовые строки. Каждая базовая строка состоит из строчных латинских букв. Базовая строка не может быть пустой, а сумма длин всех базовых строк не превосходит 106.

Следующая строка содержит единственное целое число m (1 ≤ m ≤ 2000) — количество базовых строк в Гипер Строке t.

Следующая строка содержит m целых чисел, записанных через пробел, i1, i2, ..., im (1 ≤ ij ≤ n) — индексы базовых строк, из которых составлена Гипер Строка t.

Последняя строка содержит непустую строку s. Строка s состоит только из строчных латинских букв и ее длина не превосходит 2000.

Выходные данные

Выведите единственное целое число — длину наидлиннейшей общей подпоследовательности Гипер Строки t и строки s. Если нет ни одной общей подпоследовательности, выведите 0.

Примеры
Входные данные
2
cba
dgh
2
1 2
aedfhr
Выходные данные
3
Входные данные
2
b
a
5
1 2 1 2 1
aaa
Выходные данные
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».