Composing Of String

Description:

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.

Sample Input:

3
a
aa
a
aaa

Sample Output:

2

Sample Input:

4
ab
aab
aa
bb
baaab

Sample Output:

3

Sample Input:

2
aaa
bbb
aaacbbb

Sample Output:

-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.