I. Composing Of String

Codeforces

IDCF774I

Time2000ms

Memory256MB

Difficulty—

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

Samples

Input #1

3
a
aa
a
aaa

Output #1

Input #2

4
ab
aab
aa
bb
baaab

Output #2

Input #3

2
aaa
bbb
aaacbbb

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "I. Composing Of String",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF774I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Stepan has a set of _n_ strings. Also, he has a favorite string _s_.\n\nStepan wants to do the following. He will take some strings of his set and write them down one after another. It is possible that ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments