Description

Grandmother loves writing letters, but because of her age, her letters are full of various mistakes. So zxbsmk plans to fix every erroneous sentence for her.

Since grandmother is very well educated, all the sentences she writes are English sentences, and the letters in the sentences are all lowercase. However, zxbsmk’s English is very poor, so he bought an English dictionary containing $W (1 \leq W \leq 600)$ words. Each word has a length of at most $25$ letters, and all are composed of lowercase letters.

Now let’s look at what kind of mistakes appear in grandmother’s sentences. For example, one of the sentences she wrote is catotail. This makes no sense, because an extra letter o appeared, so the correct sentence should be cattail.

It is known that grandmother’s sentence consists of $L (2 \leq L \leq 300)$ letters. Some letters are extra. Now, with the help of zxbsmk’s dictionary, please help him fix grandmother’s sentence. You must remove as few extra letters as possible so that the remaining letters form a valid sentence.

Input Format

The first line contains two integers $W$ and $L$.

The second line contains a string of length $L$, representing the sentence to be corrected.

Then follow $W$ lines, each containing one valid word.

Output Format

Output a single integer, the minimum number of letters that need to be removed.

2 8
catotail
cat
tail

1

Hint

catotail $\to$ cattail.

Translated by ChatGPT 5