KMOP

Interview

Time limit0.5sMemory limit1024 MB

Summary

Pick a prefix of 1 to 3 letters from each word so the concatenated acronym has no three consonants in a row, minimizing its length.

Level: Medium4 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

You probably know the KMP algorithm. KMP is an acronym for Knuth Morris Pratt, who published the algorithm together in 1977. How do you pronounce KMP? You can just say Knuth Morris Pratt, but how do you pronounce the acronym itself? Since KMP is not a pronounceable word, you have to say the letters one by one. This problem is about pronounceable acronyms.

A phrase is a list of words, and a word is a sequence of letters. Each letter is either a vowel or a consonant. For simplicity, the six letters A, E, I, O, U and Y are vowels, and all other letters are consonants. Whether a word is pronounceable is debatable, but here a word is pronounceable when it does not contain more than two contiguous consonants. For instance, LEMPEL is pronounceable, while DIJKSTRA is not.

Given a phrase of $N$ words, an acronym for the phrase is the concatenation of $N$ prefixes, one prefix for each word, in the order the words appear. Each prefix has at least one and at most three letters. Find the minimum length a pronounceable acronym can have.

For example, with $N = 3$ and the phrase KNUTH MORRIS PRATT, there are 27 possible acronyms, such as KMP, KMPR, KMPRA, KMOP, KMOPR and KNUMORPRA. Of these, KMOP and KMOPR are pronounceable, while the others are not. The only three-letter acronym, KMP, is not pronounceable, so KMOP is a minimum-length pronounceable acronym for this phrase.

Input

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

Each of the next $N$ lines contains a non-empty string of uppercase letters, which is a word in the phrase. The 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

Print a single line with the minimum length of a pronounceable acronym for the phrase. If no pronounceable acronym exists, print *.

Examples5

Example 1
Input
```
3
KNUTH
MORRIS
PRATT
```
Expected output
```
4
```
Example 2
Input
```
3
KNUTH
M
PRATT
```
Expected output
```
5
```
Example 3
Input
```
3
K
M
P
```
Expected output
```
*
```
Example 4
Input
```
2
K
M
```
Expected output
```
2
```
Example 5
Input
```
4
YOU
SHOULD
BE
DANCING
```
Expected output
```
5
```