最长公共前缀长度之和

题号：NC297622
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ Bingbong 给定一个长度为 $n$ 的字符串 $s$ 和一个由 $m$ 个字符串构成的数组 $\{t_1,t_2,\cdots,t_m\}$ 。
$\hspace{15pt}$ 现在你可以将 $s$ 的一个前缀删除，即选择一个 $i\left (0 \leqq i \leqq n−1\right)$ ，删除 $s$ 的前 $i$ 个字符（若 $i=0$ 则不删除），剩余后缀为 $s[i+1..n]$ 作为新的字符串。
$\hspace{15pt}$ 现在你需要最大化修改后的字符串 $s$ 与字符串数组 $t$ 中每个字符串的最长公共前缀的长度之和。并输出这个最大值。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行两个整数 ，表示字符串  的长度、数组  中的字符串个数。
第二行一个长度为  的字符串 ，其仅由小写字母组成。
接下来  行，每行一个字符串 ，其仅由小写字母组成。除此之外，保证单个测试文件的  之和、 之和不超过 。且数组  中的全部字符串长度之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，代表答案。

示例1

输入

复制

2
6 4
abdabc
abd
abc
abc
abc
3 2
aaa
aa
a

输出

复制

11
3

说明

对于第一组样例：删除前缀 ，使得 ，此时答案为 2+3+3+3=11 。
对于第二组样例，不需要删除，，此时答案为 2+1=3 。