The ABCD Murderer#9747
Oscar is a big fan of crime movies. He greatly admires how creative some of the villains can be, and now he wants to show some creativity of his own. Unfortunately, Oscar lacks experience and cannot come up with an original trick, so he decides to draw inspiration from a classic one.
Oscar has always been fascinated by the scene in which criminals cut letters out of newspapers and assemble them into a ransom note. However, he does not want to be a complete copycat. Instead, he invents his own variation of this trick: rather than assembling the message letter by letter (which he finds too boring and time-consuming), he decides to cut out whole words.
Oscar buys several mainstream newspapers, which gives him a virtually unlimited supply of paper: he can cut out any word that appears in the newspapers as many times as he needs. However, his choice is still restricted to the set of words actually printed in the newspapers — some words may simply never appear there.
To simplify things, Oscar decides to remove all punctuation and whitespace from the ransom note and to ignore letter case. 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 words he needs to cut out of the newspapers to assemble the ransom note.
The first line contains an integer l~(1 \le l \le 3 \cdot 10^5) — the number of words found in the newspapers.
The second line contains the text of the ransom note — a non-empty string consisting only of lowercase English letters. Its length does not exceed 3 \cdot 10^5.
Each of the next lines contains one word that appears in the newspapers, consisting of lowercase English letters. No word is empty or longer than the ransom note. The total length of all words does not exceed 3 \cdot 10^5. The same word may appear in the input several times.
Print one integer — the minimum number of words Oscar has to cut out of the newspapers to assemble the ransom note. Each word is counted as many times as it is actually cut out. If the ransom note cannot be assembled from the given words, print .
Example 1
Example 2
Example 3