F-快乐_牛客周赛 Round 103

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

Bingbong 给定一个长度为 $n$ 的字符串 $s$ 和一个长度为 $m$ 的字符串集合 $\{t_1,t_2,\cdots,t_m\}$ 。

现在你可以将 $s$ 的一个前缀删除，即选择一个 $i(0\leqq i\leqq n-1)$ 删除 $s[0:i]$ ，保留 $s[i+1：n-1]$ ，也可以选择不删除。

现在你需要最大化修改后的字符串 $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 。