当前没有测试数据。

快

题目描述

给定 $n$ 个仅由小写英文字母构成的字符串，第 $i$ 个字符串记为 $S_i$。

若干个字符串的匹配度定义为：他们的最长公共前缀与最长公共后缀的长度的较小值的平方。特别地，单独一个字符串的匹配度为 $0$。

你需要将所有字符串分为若干组，最大化每组字符串的匹配度之和。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行，第 $i$ 行为一个字符串 $S_i$。

输出格式

一行一个整数，表示答案。

样例 #1

样例输入 #1

4
ioi
noi
iaknoi
iakioi

样例输出 #1

4

样例 #2

样例输入 #2

3
woruoshengrikuaile
woruoshengrikuaile
woruoshengrikuaile

样例输出 #2

324

样例 #3

样例输入 #3

6
hello
world
problem
hehello
word
poem

样例输出 #3

6

提示

样例解释 1

一种最优方案是：

• ioi 单独一组，匹配度为 $0$。
• noi 单独一组，匹配度为 $0$。
• 将 iaknoi 与 iakioi 分为一组，匹配度为 $4$。

于是输出 $4$。

样例解释 2

一种最优方案是：

• 将全部 $3$ 个字符串分为一组，匹配度为 $18^2 = 324$。

于是输出 $324$。

数据范围与约定

• 对于 $16 \%$ 的测试数据，有 $2 \leq n \leq 16$，单个字符串长度不超过 $10$。
• 对于另外 $24 \%$ 的测试数据，本质不同字符串的数量不超过 $16$。
• 对于 $100 \%$ 的测试数据，有 $2 \leq n \leq 10^5$，所有字符串长度之和不超过 $2 \cdot 10^5$。
• 有 $28 \%$ 的测试数据中，所有字符串都是回文串。

保证输入字符串仅包含小写英文字母。