Minimizing the Total Cost of Learning Words

Lweb has a huge list of English words to learn before he can play his favorite game. His teacher, Feng, gives him a plan table listing n words in some order. The cost to learn each word depends on its position in the plan and on its suffix relationships with other words. More formally, you are given n distinct strings. You need to arrange them in a permutation so that the total cost is minimized. The cost for a string s placed at position x (1-indexed) is determined as follows:

• If there exists at least one other string t that is a suffix of s (i.e. s ends with t) and t is placed at some position > x, then the cost for s is \(n^2\).
• If no other string is a suffix of s (that is, there is no string t with \(t \neq s\) such that \(s\) ends with \(t\)), then the cost for s is x.
• If all strings that are suffixes of s appear before s and the maximum index among such strings is \(y\), then the cost for s is \(x-y\). (Note that when a string has at least one suffix among the other strings, condition 3 applies provided the ordering is chosen so that every suffix appears earlier than s.)

Since the penalty \(n^2\) is huge, any optimal ordering must ensure that for every pair of distinct strings \(s\) and \(t\) with t a suffix of s, t is placed before s in the ordering. A natural strategy is to order the strings in increasing order of their lengths (if two strings have equal length, any order is acceptable as no suffix relation can occur between them). This ordering guarantees that if t is a suffix of s, then \(|t| \le |s|\) and thus t appears before s.

After choosing an ordering that respects the suffix conditions, the cost for each string s at position \(x\) can be computed as follows:

• If s has no other string that is its suffix, the cost is \(x\).
• If s does have one or more suffix strings (all placed before s), let \(y\) be the maximum position among them; then the cost is \(x - y\).

Your task is to compute the minimum total cost obtained by a valid ordering of the n strings.

inputFormat

The first line contains an integer n (the number of strings).

Each of the following n lines contains a non-empty string consisting of English letters.

outputFormat

Output a single integer, which is the minimum total cost of learning all the words under the optimal ordering.

sample

2
a
ba

2