The cows have a dictionary, you know. It contains W (6 <= W <= 1000) words, each at most 20 characters long. Because their cowmunication system, based on mooing, is not very accurate, sometimes they hear words that do not make any sense. For instance, Bessie once received a message that said "browndcodw." As it turns out, the intended message was "browncow" and the two letter "d"s were noise from other parts of the barnyard. The cows want you to help them decipher a received message of lengthL (2 <= L <= 1600) characters that is a bit garbled. In particular, they know that the message has some extra letters, and they want you to determine the smallest number of letters that must be removed to make the message a sequence of words from the dictionary.

* Line 1: Two space-separated integers, respectively W and L * Line 2: L characters (followed by a newline, of course): the received message (the message contains only the characters 'a'..'z') * Lines 3..W+2: The dictionary, one word per line; words consist only of the characters 'a'..'z'.

A single line with a single integer that is the smallest number of characters that need to be removed to make the message a sequence of dictionary words.

USAICO 2006 Day 5