Christmalo.win

Time limit1sMemory limit1024 MB

Summary

Given N short strings, pick two and a shared letter to splice their prefix and suffix, minimizing the total deleted characters.

Level: Medium6 of 10
Topics: String, Hash map, Brute force, Implementation
Solved: No attempts yet

Problem

Kipa, who is leading the worldwide Ki-pop craze, is deep in thought ahead of the release of a new album destined for the history books.

What should the title be?

Kipa's albums have a tradition of always using a word made the same way. According to the tradition, Kipa picks two words that fit the album, chooses one alphabet letter common to both words, deletes the characters after that letter in the word that comes first, deletes the characters before that letter in the word that comes second, and then joins the two words to make the new album title. If the same letter appears multiple times, any one of them may be chosen.

For example, given christmas and halloween, choosing the common letter a produces christma and alloween, and joining them gives christmalloween.

Kipa has already picked N words that fit the album, but has left the task of choosing the title to you with the request that the number of deleted characters be minimized, and has gone off to record. Given Kipa's personality, you must decide on the title before Kipa returns!

Input

The first line gives the number of strings N. The following N lines give distinct strings Si. Each string consists only of lowercase alphabet letters and has at most 20 characters.

2 ≤ N ≤ 105
2 ≤ |Si| ≤ 20
Si ≠ Sj if i ≠ j

Output

Print the minimum number of deleted characters when a word satisfying the given conditions is made. If no word satisfying the given conditions can be made, print -1.

Examples3

Example 1
Input
```
2
christmas
halloween
```
Expected output
```
2
```
Example 2
Input
```
3
abc
bbc
defg
```
Expected output
```
1
```
Example 3
Input
```
4
aaaa
bbbb
cccc
dddd
```
Expected output
```
-1
```