吊坠
题号：NC309396
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小蓝想制作一个吊坠，他手上有 n 个长度为 m 的首尾相连的环形字符串 \{s_1, s_2, \cdots, s_n\}，他想用 n-1 条边将这 n 个字符串连接起来做成吊坠，要求所有的字符串连完后形成一个整体。连接两个字符串 s_i, s_j 的边的边权为这两个字符串的最长公共子串的长度（可以按环形旋转改变起始位置，但不能翻转），小蓝希望连完后的这 n-1 条边的边权和最大，这样的吊坠他觉得最好看，请计算最大的边权和是多少。

输入描述:

输入的第一行包含两个正整数 n, m，用一个空格分隔。

接下来 n 行，每行包含一个长度为 m 的字符串，分别表示 s_1, s_2, \cdots, s_n。

输出描述:

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

输入

复制 
4 4
aabb
abba
acca
abcd

输出

复制 
8

说明

连接 \langle 1, 2 \rangle, \langle 2, 3 \rangle, \langle 2, 4 \rangle，边权和为 4 + 2 + 2 = 8。
(注：1和2是 "aabb" 和 "abba"，旋转后可以完全重合，LCS为4；2和3 "abba" 和 "acca" LCS为 "a" 或 "b" ? 不，应该是 "a"和"a"拼接? "abba"旋转成"bbaa", "acca"旋转"caac", 中间有"aa"。最大应该是2，比如 "ab" 或 "aa")。

备注:

- 对于 20% 的评测用例，1 \le n, m \le 10；
- 对于所有评测用例，1 \le n \le 200, 1 \le m \le 50。所有字符串由小写英文字母组成。