У Степана есть набор из n строк. Также у него есть любимая строка s.
Степан хочет сделать следующее. Он будет брать какие-то строки из своего набора и выписывать их одну за другой. Возможно, что какие-то строки он возьмет более одного раза, а какие-то не возьмет вовсе.
Перед вами стоит задача определить минимальное количество строк, которые нужно взять Степану из набора и выписать таким образом, чтобы строка s встречалась как подпоследовательность в получившейся написанной строке. Каждую строку из набора нужно считать столько раз, сколько Степан брал её из набора.
Например, в строке «abcd» строки «ad», «acd», «abcd» встречаются как подпоследовательности, а строки «ba», «abdc» нет.
Выходные данные
Выведите минимальное количество строк, которые нужно взять Степану из набора и выписать таким образом, чтобы строка s встречалась как подпоследовательность в получившейся написанной строке. Каждую строку из набора нужно считать столько раз, сколько Степан брал её из набора.
Если ответа не существует, выведите -1.
Примечание
В первом примере Степан может взять, например, третью и вторую строки из набора, выписать их, и получить в точности свою любимую строку.
Во втором примере Степан может взять, например, вторую, третью и вновь вторую строки из набора и выписать их. Тогда у него получится строка «aabaaaab», в которой как подпоследовательность содержится его любимая строка «baaab».
В третьем примере Степан никак не сможет получить свою любимую строку, так как в ней есть буква «c», которой нет ни в одной из строк набора.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
a
aa
a
aaa
|
2
|
|
2
|
4
ab
aab
aa
bb
baaab
|
3
|
|
3
|
2
aaa
bbb
aaacbbb
|
-1
|