P16750 [GKS 2020 #A] Bundling

Pip 有 $N$ 个字符串。每个字符串仅由 A 到 Z 的字母组成。Pip 希望将这些字符串分成大小为 $K$ 的**组**。每个字符串必须恰好属于一个组。 一个组的得分等于该组中所有字符串共享的最长前缀的长度。例如： - 组 {RAINBOW, RANK, RANDOM, RANK} 的得分为 $2$（最长前缀为 “RA”）。 - 组 {FIRE, FIREBALL, FIREFIGHTER} 的得分为 $4$（最长前缀为 “FIRE”）。 - 组 {ALLOCATION, PLATE, WORKOUT, BUNDLING} 的得分为 $0$（最长前缀为 “”）。 请帮助 Pip 将字符串分成大小为 $K$ 的组，使得各组得分之和最大。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $K$。随后 $N$ 行，每行包含 Pip 的一个字符串。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是可能的最大得分之和。

在样例 #1 中，Pip 可以通过以下分组获得总分 $0$： - $\{\text{KICK}, \text{START}\}$，得分为 $0$。 在样例 #2 中，Pip 可以通过以下分组获得总分 $10$： - $\{\text{G}, \text{G}\}$，得分为 $1$。 - $\{\text{GO}, \text{GO}\}$，得分为 $2$。 - $\{\text{GOO}, \text{GOO}\}$，得分为 $3$。 - $\{\text{GOOO}, \text{GOOO}\}$，得分为 $4$。 ### 限制条件 $1 \le T \le 100$。 $2 \le N \le 10^5$。 $2 \le K \le N$。 $K$ 能整除 $N$。 Pip 的每个字符串至少包含一个字符。 每个字符串仅由 A 到 Z 的字母组成。 **测试集 1** Pip 的每个字符串至多包含 $5$ 个字符。 **测试集 2** 所有测试用例中 Pip 的字符串的总字符数不超过 $2 \times 10^6$。 翻译由 DeepSeek V4 Pro 完成