CF2005C Lazy Narek

$\text{Alice}$ 有 $n$ 个字符串，每个字符串长度为 $m$。 $\text{Alice}$ 会选择 $n$ 个字符串的一个子集，可以为空，将子集中的字符串首尾按原本的相对顺序拼接，然后她会在拼接的字符串中依次查找字符 "n","a","r","e","k"。当这五个字符全被找到后，$\text{Alice}$ 会将自己的分数 $+5$ 然后继续从当前位置向后查找。 之后 $\text{Bob}$ 会扫描整个字符串并查找，如果 $\text{Alice}$ 的查找中有未被访问的 "n","a","r","e" 或 "k"，$\text{Bob}$ 会将自己的分数 $+1$。 请你帮 $\text{Alice}$ 和 $\text{Bob}$ 求出 $\max\{score_{Alice} - score_{Bob}\}$。

多组测试数据，第一行一个正整数 $T(1 \leq T \leq 10^5)$，表示数据组数。 接下来每个测试数据的第一行两个正整数 $n,m(1 \leq n,m \leq 10^3)$，表示字符串的数量以及每个字符串的长度。 接下来 $n$ 行，每行一个长度为 $m$ 的字符串，意义如题意所述，仅包含小写字母。 $\sum{n \cdot m} \leq 10^6$

对于每个测试数据，输出一个整数：$score_{Alice} - score_{Bob}$ 的最大值

In the first test case, one of the optimal answers is when Narek doesn't choose any of the strings, so the answer is $ 0 $ . He can alternatively choose all the strings. In this case, the full string becomes "nnaarreekk". Narek can choose the first appearances of all letters and add $ 5 $ to the score. His opponent will add $ 1 $ for all second appearances, which will be $ 5 $ in total. So the answer will be $ 5 - 5 = 0 $ . In the third test case, the only optimal answer is when Narek doesn't choose the string. Note that if he were to choose the string, he wouldn't be able to find the last letter "k", so his score would stay at $ 0 $ instead of becoming $ 5 $ . Then ChatGPT would add $ 4 $ for all of the $ 4 $ letters, and the answer would become $ 0 - 4 = -4 $ . In the last test case, Narek needs to choose the first and the last strings. After putting these two next to each other, he gets " $ {\color{red}{n}}rr{\color{red}{a}}{\color{red}{r}}{\color{red}{e}}{\color{red}{k}}{\color{red}{n}}k{\color{red}{a}}{\color{red}{r}}{\color{red}{e}}{\color{red}{k}}{\color{blue}{z}} $ ". Narek can choose the letters marked with red and add $ 10 $ to his score. Since the black colored letters Narek left behind are eligible for the opponent to claim (they are used in the word "narek"), the opponent adds all other letters to the score and gets a score of $ 3 $ . Therefore, the answer is $ 10 - 3 = 7 $ .