31761번 - KMOP 다국어

문제

You probably know the KMP algorithm. You may also know that “KMP” is an acronym that stands for “Knuth Morris Pratt”, who jointly published the algorithm in 1977. How do you pronounce “KMP”? Of course, you can just say “Knuth Morris Pratt”, but what about pronouncing the acronym itself? Since “KMP” is not a pronounceable word, you are forced to say the letters one by one. In this problem we are interested in pronounceable acronyms.

We need a few definitions to formalize the requirement. A phrase is a list of words and a word is a sequence of letters. Each letter is either a vowel or a consonant. Deciding whether a letter is a vowel or a consonant depends on the language and other elements. For simplicity, we say that the six letters “A”, “E”, “I”, “O”, “U” and “Y” are vowels, while all the rest are consonants. Although it is debatable whether a given word is pronounceable, we say that a word is pronounceable when it does not contain more than two contiguous consonants. For instance, “LEMPEL” is a pronounceable word, while “DIJKSTRA” is not.

Given a phrase composed of $N$ words, an acronym for the phrase is the concatenation of N prefixes, one prefix for each word, in the order they appear in the phrase. Each prefix must have at least one and at most three letters. Your task is to determine the minimum length a pronounceable acronym can have.

As an example with $N = 3$ consider the phrase “KNUTH MORRIS PRATT”. There are 27ドル$ possible acronyms for this phrase, such as “KMP”, “KMPR”, “KMPRA”, “KMOP”, “KMOPR” and “KNUMORPRA”, among others. Some of these acronyms are pronounceable (“KMOP” and “KMOPR”), while some others not (“KMP”, “KMPR”, “KMPRA” and “KNUMORPRA”). Since the only three-letter acronym “KMP” is not pronounceable, it follows that “KMOP” is a minimum-length pronounceable acronym for the phrase.

입력

The first line contains a positive integer $N$ indicating the number of words in the phrase.

Each of the next $N$ lines contains a non-empty string made of uppercase letters representing a word in the phrase. Words are given in the order they appear in the phrase. The sum of the lengths of all the strings is at most 10ドル^6$.

출력

Output a single line with an integer indicating the minimum length a pronounceable acronym can have, or the character “*” (asterisk) if no pronounceable acronym exists for the phrase.

제한

힌트