Migrated from Lutece 2825 解密程序

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在某个时间线上，ljj 抛弃了作为卷怪的身份，成为了一名躬耕与黑暗，侍奉于光明的刺客。而在今晚，ljj 准备潜入敌人的要塞获取同僚 NamelessOIer 提供的情报，并借此找出敌人老大的位置。已知情报内容是 n 个字符串，解密出的信息是一个数字，ljj 持有解密程序。但由于疏忽大意，装着程序的 U 盘掉进了信仰之跃的草堆，再也不见了踪影。于是 ljj 找上了你，想让你还原出这份解密程序。程序的大致流程如下：

给定的 n 个字符串，据此构造一个 n 个点的无向图：图中 $i,j$ 两个点之间的边权是串 $s_{i},s_{j}$ 的最长公共子串长度 LCS。接下来他要对这个无向图求最大生成树，求最大生成树的权值

Input

第一行读入一个整数 n ，表示字符串数量

接下来 n 行，每行读入一个字符串$s_{i}$，意义如题意所示

Output

输出一个整数，表示最大生成树的权值

Samples

5
btmlgb
nnntg
sbha
nbnkgma
cl

4

2
yydz
jdw

1

9
g
gn
gns
gnss
gnssw
nssw
ssw
sw
w

20

Constraints

$n\le 2\times 10^{6}$，所有串总长$\sum|S|\le 2\times 10^{6}$

Note

T了不一定是卡常，可能是做法不够优秀

Resources

2022 UESTC ICPC Training for String and Search Algorithm