题目描述

给定 $n$ 个由小写英文字母组成的字符串 $s_1,s_2,...,s_n$，定义前缀总分为 $V=\sum_{i<j}P(s_i,s_j)$ 其中 $P(s_i,s_j)$ 表示 $s_i,s_j$ 的最长公共前缀的长度。

小蓝可以选择其中一个字符串，并修改其中的一个字符。请问修改后前缀总分最大为多少？

输入格式

输入的第一行包含一个正整数 $n$。

接下来 $n$ 行，每行包含一个字符串 $s_i$。

输出格式

输出一行包含一个整数表示答案。

3 
aab 
bbb 
abb

5

解释 #1

将第二个字符串改为 $abb$，得分为 $P(aab,abb)+P(aab,abb)+P(abb,abb)=1+1+3=5$。

数据范围

• 对于 $20\%$ 的评测用例，$1≤n≤20$;

• 对于所有评测用例，$1≤n≤200$，$1≤|s_i|≤200$，其中 $|s_i|$ 表示 $s_i$ 的长度。