Maximum Spanning Tree on Complete Graph with Longest Common Substring Weights

You are given a complete undirected graph with n vertices and n strings s₁, s₂, ..., s_n. There is an edge between every pair of vertices i and j with weight equal to the length of the longest common substring (LCS) between s_i and s_j. A substring is defined as a contiguous sequence of characters obtained by removing some (possibly zero) characters from the beginning and/or the end of the string. For example, maca, aca and cau are substrings of macau, while acu is not.

Your task is to compute the maximum total weight of any spanning tree in this graph. A spanning tree of a graph with n vertices is a tree connecting all vertices and consisting of exactly n-1 edges.

The weight of the spanning tree is defined as the sum of the weights of its edges. Use the standard maximum spanning tree algorithm (which is analogous to MST but selecting edges in descending order) to solve the problem.

Note: If there are any mathematical formulas, they must be formatted in LaTeX. For example, the weight of the edge between vertices \( i \) and \( j \) is given by:

[ w(i,j)= \text{LCS}(s_i,s_j) ]

inputFormat

The first line contains an integer n \( (2 \le n \le 100) \) representing the number of vertices (and strings).

Then n lines follow, each containing a non-empty string \( s_i \). It is guaranteed that the strings consist of lowercase and/or uppercase English letters.

outputFormat

Output a single integer representing the maximum total weight of any spanning tree on the graph.

sample

3
abc
bcd
cde

4