Migrated from Lutece 2984 只因你太美

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

第一次要变成这样的我，不管我怎么去否认。只因你太美，baby；只因你实在是太美，baby……

听着耳机里熟悉的旋律，$\text{Bob Wang}$ 也觉得这首歌有一种说不出的美，所以他打算写一首同样这么美的歌。但由于创作水平匮乏，他写出的歌都有一种脑干缺失的美。没办法，他只好从他认为美的歌里仿写一些歌词，再把它们拼接起来，让他的拙作尽可能美。

一首歌可以看做一个长度为 $n$ 的字符串 $S$。$\text{Bob Wang}$ 会仿写出若干条歌词 $t_i$，这些歌词长度相等，且长度之和为 $n$。之后 $\text{Bob Wang}$ 会把这些歌词按照一定的顺序收尾拼接，最终形成一个长度也为 $n$ 的字符串 $T$。

假设有一条歌词 $t_i$ 在 $T$ 中的位置为 $l\sim r$，$\text{Bob Wang}$ 定义这条歌词的美丽度为 $T_{l\cdots r}$ 与 $S_{l\cdots r}$ 的最长相同前缀的长度，即 $\max\{len\mid S_{l\cdots l+len-1}=T_{l\cdots l+len-1},0\le len\le r-l+1\}$，其中 $S_{i\cdots i-1}$ 和 $T_{i\cdots i-1}$ 被定义为空串。整首曲子的美丽度即所有歌词的美丽度之和。

现在 $\text{Bob Wang}$ 给了你原曲 $S$，以及他仿写的若干条歌词 $t_i$。他希望你可以帮助他决定排列歌词的顺序，使得他写的曲子 $T$ 的美丽度最大。

Input

第一行两个整数 $n$ 和 $m$，表示原曲的长度以及歌词的条数，保证 $m\mid n$；

第二行一个由小写字符组成的字符串 $S$，表示原曲；

接下来 $m$ 行，每行一个字符串，表示歌词 $t_i$，保证歌词的长度均为 $\frac nm$。

Output

一行一个整数，表示排列歌词可以得到的歌曲的最大美丽度。

Samples

15 3
helloohalaoollo
helno
oohds
apple

5

Constraints

$1\leq n\leq 10^6$，$m\mid n$。

Note

对于样例，最终的歌曲为 helnoappleoohds，其中 helno 的美丽度为 $3$，oohds 的美丽度为 $2$，apple 的美丽度为 $0$，整首歌的美丽度为 $5$，可以证明这样排列歌词得到的歌曲的美丽度最大。

Resources

2023 UESTC ICPC Training for String