codeforces#P774I. Composing Of String
Composing Of String
Description
Stepan has a set of n strings. Also, he has a favorite string s.
Stepan wants to do the following. He will take some strings of his set and write them down one after another. It is possible that he will take some strings more than once, and will not take some of them at all.
Your task is to determine the minimum number of strings in the set which Stepan needs to take and write so that the string s appears as a subsequence in the resulting written down string.
For example, in the string "abcd" strings "ad", "acd", "abcd" appear as subsequences, and strings "ba", "abdc" don't appear as subsequences.
The first line contains the integer n (1 ≤ n ≤ 50) — the number of strings in Stepan's set.
The next n lines contain n non-empty strings consisting of lowercase letters of the English alphabet. The length of each of these strings does not exceed 50 symbols. It is possible that some strings from Stepan's set are the same.
The next line contains the non-empty string s, consisting of lowercase letters of the English alphabet — Stepan's favorite string. The length of this string doesn't exceed 2500 symbols.
Print the minimum number of strings which Stepan should take from the set and write them down one after another so that the string s appears as a subsequence in the resulting written down string. Each string from the set should be counted as many times as Stepan takes it from the set.
If the answer doesn't exsist, print -1.
Input
The first line contains the integer n (1 ≤ n ≤ 50) — the number of strings in Stepan's set.
The next n lines contain n non-empty strings consisting of lowercase letters of the English alphabet. The length of each of these strings does not exceed 50 symbols. It is possible that some strings from Stepan's set are the same.
The next line contains the non-empty string s, consisting of lowercase letters of the English alphabet — Stepan's favorite string. The length of this string doesn't exceed 2500 symbols.
Output
Print the minimum number of strings which Stepan should take from the set and write them down one after another so that the string s appears as a subsequence in the resulting written down string. Each string from the set should be counted as many times as Stepan takes it from the set.
If the answer doesn't exsist, print -1.
Samples
3
a
aa
a
aaa
2
4
ab
aab
aa
bb
baaab
3
2
aaa
bbb
aaacbbb
-1
Note
In the first test, Stepan can take, for example, the third and the second strings from the set, write them down, and get exactly his favorite string.
In the second example Stepan can take, for example, the second, the third and again the second strings from the set and write them down. Then he will get a string "aabaaaab", in which his favorite string "baaab" is a subsequence.
In the third test Stepan can not get his favorite string, because it contains the letter "c", which is not presented in any of the strings in the set.