P2432 zxbsmk Loves Checking Errors

During the summer vacation, zxbsmk went back to his hometown and met his grandmother. However, he ran into a problem.

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.

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 a single integer, the minimum number of letters that need to be removed.

`catotail` $\to$ `cattail`. Translated by ChatGPT 5