题目描述

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

输入格式

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

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，分别表示 $s1, s2, · · · , sn$。

输出格式

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

4 4
aabb
abba
acca
abcd

8

解释 #1

连接 $< 1, 2 >, < 2, 3 >, < 2, 4 >$，边权和为 $4 + 2 + 2 = 8$。

数据范围

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