P16750 [GKS 2020 #A] Bundling

Pip has $N$ strings. Each string consists only of letters from A to Z. Pip would like to bundle their strings into *groups* of size $K$. Each string must belong to exactly one group. The score of a group is equal to the length of the longest prefix shared by all the strings in that group. For example: * The group {RAINBOW, RANK, RANDOM, RANK} has a score of $2$ (the longest prefix is 'RA'). * The group {FIRE, FIREBALL, FIREFIGHTER} has a score of $4$ (the longest prefix is 'FIRE'). * The group {ALLOCATION, PLATE, WORKOUT, BUNDLING} has a score of $0$ (the longest prefix is ''). Please help Pip bundle their strings into groups of size $K$, such that the sum of scores of the groups is maximized.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing the two integers $N$ and $K$. Then, $N$ lines follow, each containing one of Pip's strings.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum sum of scores possible.

In Sample Case #1, Pip can achieve a total score of $0$ by making the groups: * $\{\text{KICK}, \text{START}\}$, with a score of $0$. In Sample Case #2, Pip can achieve a total score of $10$ by making the groups: * $\{\text{G}, \text{G}\}$, with a score of $1$. * $\{\text{GO}, \text{GO}\}$, with a score of $2$. * $\{\text{GOO}, \text{GOO}\}$, with a score of $3$. * $\{\text{GOOO}, \text{GOOO}\}$, with a score of $4$. ### Limits $1 \le T \le 100$. $2 \le N \le 10^5$. $2 \le K \le N$. $K$ divides $N$. Each of Pip's strings contain at least one character. Each string consists only of letters from A to Z. **Test Set 1** Each of Pip's strings contain at most $5$ characters. **Test Set 2** The total number of characters in Pip's strings across all test cases is at most $2 \times 10^6$.