前缀总分

题目描述

给定 $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$ 。

输出格式

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

样例 #1

样例输入 #1

3
aab
bbb
abb

样例输出 #1

5

提示

【样例说明】

将第二个字符串改为 $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$ 的长度。