Word Chain

Time limit2sMemory limit128 MB

Summary

Given up to 16 vowel-only words, chain them by matching first and last letters without repeats to maximize the total length used.

Level: Medium6 of 10
Topics: Bit manipulation, Dynamic programming, Graph
Solved: No attempts yet

Problem

Choose words from a dictionary and arrange them in order. The last letter of each word must be the same as the first letter of the next word.

Only words in the dictionary may be used, and the same word cannot be used more than once. Every dictionary word consists only of the uppercase vowels A, E, I, O, and U. The first word may be any word.

The score is the sum of the lengths of the used words. Find the maximum score obtainable by arranging words according to the rule.

Input

The first line contains the number of dictionary words N. (1 ≤ N ≤ 16)

Each of the next N lines contains one dictionary word. Each word consists only of the uppercase letters A, E, I, O, and U, and its length is at most 100. No word is given more than once.

Output

Print one line containing the maximum score obtainable by arranging the words according to the rule.

Examples3

Example 1
Input
```
3
AEIOU
UIU
EO
```
Expected output
```
8
```
Example 2
Input
```
4
AEEEO
OEOAEEE
AO
O
```
Expected output
```
13
```
Example 3
Input
```
5
IOO
IUUO
AI
OIOOI
AOOI
```
Expected output
```
16
```