Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

This round has an unusual addition to the rules. For each problem you must use distinct language. Thus, if you have a submission that has passed at least one test or is being tested at the moment, then for this task you can use only this language and can not use it for other tasks. More details can be read by the link. Different implementations of the same language are considered to be the same language (for example, in C++ you can only solve one problem, regardless of the exact chosen compiler).

No tag edit access

В условии задачи недавно были сделаны правки. Просмотреть изменения.

×
I. Composing Of String

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

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.

Examples

Input

3

a

aa

a

aaa

Output

2

Input

4

ab

aab

aa

bb

baaab

Output

3

Input

2

aaa

bbb

aaacbbb

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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/30/2020 04:53:29 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|