Algorithms and Data Structures

The Reference String

You are given a list of strings, each consisting of lowercase Latin letters. We will call a string , consisting of lowercase Latin letters and the character '#', a reference string if, for every string in the list, it is possible to choose some index in such that ≠ ‘#’ and selecting all indices from to the next occurrence of '#' (not inclusive) will result in the respective string. The reference string should always end with the character ‘#’.
Write a program that determines the length of the shortest reference string that satisfies the above condition, given the list of strings.

Input

The first line of the input contains a single integer, n (), representing the number of strings in the list.
The following n lines contain the strings. Each string consists of lowercase Latin letters and has a length of at most 10.

Output

Output a single integer, representing the length of the shortest reference string that satisfies the condition.

Examples

Input
Output
6 found profound ground round wound und
22
3 ab bc cd
9

Explanation

In the first example one of the shortest reference strings is the string ‘ground#profound#wound# ’
In the second example one of the shortest reference strings is the string ‘ab#bc#cd#’
 

Constraints

Time limit: 2.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in