Problem Description

Translated from [CERC2018] The ABCD Murderer.

Oscar really likes watching crime movies. He admires criminals because they are creative. He also wants to show his creativity. But unfortunately, he has little experience and cannot come up with any original tricks. So he wants to get inspiration from existing methods. He has always liked the scene where criminals cut letters out of newspapers and use them to form a ransom note. However, Oscar does not want to copy others, so he came up with his own variation of this method. He thinks that forming a text letter by letter is both boring and time-consuming. So he decided to create his ransom note by cutting out whole words instead.

Oscar bought some mainstream newspapers, so he has an almost unlimited word supply. He can cut out any specific word multiple times. However, he is still limited by the set of words that actually appear in the newspapers. The problem is that some words never appear in the newspapers at all. To make the task easier, he decided to remove all punctuation and spaces from the ransom note and ignore letter case. He also allows cut-out words to overlap, as long as the overlapping parts are identical. Now Oscar wants to know the minimum number of words he needs to cut out to form the ransom note he wants.

Input Format

The first line contains an integer $L$, representing the number of words found in the newspapers.

The next line contains the ransom note content $s$. It is guaranteed to be non-empty and to contain only lowercase English letters.

The next $L$ lines each contain a word $a_i$ that appears in the newspapers, guaranteed to contain only lowercase English letters. None of these words is an empty string, and no word is longer than the ransom note. Every word that appears in the newspapers appears at least once in the input.

Output Format

Output the minimum number of words Oscar must cut out from the newspapers to form the ransom note. If it is impossible, output $-1$. Each word should be counted according to how many times it is actually cut out from the newspapers.

3
aaaaa
a
aa
aaa

2

5
abecedadabra
abec
ab
ceda
dad
ra

5

9
icpcontesticpc
international
collegiate
programming
contest
central
europe
regional
contest
icpc

3

Hint

Constraints: $1≤L,|s|,∑|a_i|≤3×10^5$.

Translated by ChatGPT 5