The Reference String
You are given a list of
n strings, each consisting of lowercase Latin letters. We will call a string s, 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 i in s such that ≠ # and selecting all indices from i 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 (1 ≤ n ≤ 100 000), 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
The program should print 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
- Example 1: one of the shortest reference strings is the string ‘
ground#profound#wound#
- Example 2: one of the shortest reference strings is the string ‘
ab#bc#cd#’
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB