题目描述

小蓝想制作一个吊坠，他手上有 $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$。

输出格式

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

4 4
aabb
abba
acca
abcd

8

提示

【样例说明】

连接 $\langle 1,2\rangle, \langle 2,3\rangle, \langle 2,4\rangle$，边权和为 $4 + 2 + 2 = 8$

【评测用例规模与约定】

对于 $20\%$ 的评测用例，$1 \leq n, m \leq 10$；

对于所有评测用例，$1 \leq n \leq 200$，$1 \leq m \leq 50$。所有字符串由小写英文字母组成。