Problem Description

Translated from CERC2018

Oscar is particularly fond of crime movies. He admires the criminals for their creativity. He also wants to showcase his creativity. Unfortunately, he lacks experience and cannot come up with any original tricks. Therefore, he seeks inspiration from existing methods. He has always enjoyed the scenes where criminals cut out letters from newspapers and use them to compose extortion letters. However, Oscar does not want to plagiarize, so he thought of a variation of this method. He finds it tedious and time-consuming to assemble text letter by letter. Thus, he decided to cut out entire words to compose his extortion letter.

Oscar bought some mainstream newspapers, giving him almost an unlimited word bank. He can cut out any specific word multiple times. However, he is still limited by the set of words that appear in the newspapers. The problem is that some words do not appear in the newspapers at all. To make the task simpler, he decided to remove all punctuation marks and spaces from the extortion letter and ignore the case of the letters. He also allows the cut-out words to overlap, as long as the overlapping parts are identical. Now, Oscar wants to know the minimum number of times he needs to cut out words to compose his desired extortion letter.

Input Format

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

The next line contains the content of the extortion letter $s$. It is guaranteed to be non-empty and contains only lowercase English letters.

The following $L$ lines each contain a word $a_i$ that appears in the newspapers, consisting only of lowercase English letters. None of these words are empty, nor are they longer than the extortion letter. All words from the newspapers appear at least once in the input.

Output Format

Output the minimum number of times Oscar needs to cut out words from the newspapers to compose the extortion letter. If it is not possible to compose the letter, output $-1$. Each word must be counted as many times as it is cut out from the newspapers.

Sample Input and Output

Sample Input #1

3
aaaaa
a
aa
aaa

Sample Output #1

2

Sample Input #2

5
abecedadabra
abec
ab
ceda
dad
ra

Sample Output #2

5

Sample Input #3

9
icpcontesticpc
international
collegiate
programming
contest
central
europe
regional
contest
icpc

Sample Output #3

3

Notes

$1 \leq L, |s|, \sum |a_i| \leq 3 \times 10^5$

见题面 Input 部分

见题面 Output 部分