시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 (추가 시간 없음) 1024 MB64466.667%

문제

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, TT 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.

제한

  • 1 ≤ T ≤ 100.
  • 2 ≤ N ≤ 105.
  • 2 ≤ K ≤ 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 (14점)

  • Each of Pip's strings contain at most 5 characters.

Test Set 2 (21점)

The total number of characters in Pip's strings across all test cases is at most 2 × 106.

예제 입력 1

2
2 2
KICK
START
8 2
G
G
GO
GO
GOO
GOO
GOOO
GOOO

예제 출력 1

Case #1: 0
Case #2: 10

In Sample Case #1, Pip can achieve a total score of 0 by making the groups:

  • {KICK, START}, with a score of 0.

In Sample Case #2, Pip can achieve a total score of 10 by making the groups:

  • {G, G}, with a score of 1.
  • {GO, GO}, with a score of 2.
  • {GOO, GOO}, with a score of 3.
  • {GOOO, GOOO}, with a score of 4.

예제 입력 2

1
6 3
RAINBOW
FIREBALL
RANK
RANDOM
FIREWALL
FIREFIGHTER

예제 출력 2

Case #1: 6

In Sample Case #1, Pip can achieve a total score of 6 by making the groups:

  • {RAINBOW, RANK, RANDOM}, with a score of 2.
  • {FIREBALL, FIREWALL, FIREFIGHTER}, with a score of 4.

채점 및 기타 정보

  • 예제는 채점하지 않는다.