P1278 Word Game

Io and Ao are playing a word game. They take turns saying a word that contains only vowels, and the first letter of each new word must be the same as the last letter of the previous word. The game can start from any word. No word may be said twice, and only words contained in the given dictionary may be used during the game. The complexity of the game is defined as the total sum of the lengths of the words used in the game. Write a program to compute the maximum possible complexity achievable when playing this game using a given dictionary.

The first line of the input file contains a natural number $N(1 \le N \le 16)$, where $N$ is the number of words in the dictionary. Each of the following $N$ lines contains one word from the dictionary. Each word is a string consisting only of the letters 'A', 'E', 'I', 'O', and 'U'. The length of each word is less than or equal to $100$. All words are different.

The output file contains a single line, which is the maximum possible complexity of the game.

Translated by ChatGPT 5