I. Составление строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Степана есть набор из n строк. Также у него есть любимая строка s.

Степан хочет сделать следующее. Он будет брать какие-то строки из своего набора и выписывать их одну за другой. Возможно, что какие-то строки он возьмет более одного раза, а какие-то не возьмет вовсе.

Перед вами стоит задача определить минимальное количество строк, которые нужно взять Степану из набора и выписать таким образом, чтобы строка s встречалась как подпоследовательность в получившейся написанной строке. Каждую строку из набора нужно считать столько раз, сколько Степан брал её из набора.

Например, в строке «abcd» строки «ad», «acd», «abcd» встречаются как подпоследовательности, а строки «ba», «abdc» нет.

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

В первой строке следует целое число n (1 ≤ n ≤ 50) — количество строк в наборе Степана.

В следующих n строках следуют n непустых строк, состоящих из строчных букв латинского алфавита. Длина каждой их этих строк не превосходит 50 символов. Возможно, что некоторые строки из набора Степана одинаковы.

В следующей строке следует непустая строка s, состоящая из строчных букв латинского алфавита — любимая строка Степана. Длина этой строки не превышает 2500 символов.

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

Выведите минимальное количество строк, которые нужно взять Степану из набора и выписать таким образом, чтобы строка s встречалась как подпоследовательность в получившейся написанной строке. Каждую строку из набора нужно считать столько раз, сколько Степан брал её из набора.

Если ответа не существует, выведите -1.

Примеры
Входные данные
3
a
aa
a
aaa
Выходные данные
2
Входные данные
4
ab
aab
aa
bb
baaab
Выходные данные
3
Входные данные
2
aaa
bbb
aaacbbb
Выходные данные
-1
Примечание

В первом примере Степан может взять, например, третью и вторую строки из набора, выписать их, и получить в точности свою любимую строку.

Во втором примере Степан может взять, например, вторую, третью и вновь вторую строки из набора и выписать их. Тогда у него получится строка «aabaaaab», в которой как подпоследовательность содержится его любимая строка «baaab».

В третьем примере Степан никак не сможет получить свою любимую строку, так как в ней есть буква «c», которой нет ни в одной из строк набора.