묶음 만들기

Pip은 N개의 문자열을 가지고 있다. 각 문자열은 A부터 Z까지의 문자로만 이루어져 있다. Pip은 자신의 문자열을 크기가 K인 그룹들로 묶으려고 한다. 각 문자열은 정확히 하나의 그룹에 속해야 한다.

그룹의 점수는 그 그룹의 모든 문자열이 공유하는 가장 긴 접두사의 길이와 같다. 예를 들면 다음과 같다.

• 그룹 {RAINBOW, RANK, RANDOM, RANK}의 점수는 2이다(가장 긴 접두사는 'RA'이다).

• 그룹 {FIRE, FIREBALL, FIREFIGHTER}의 점수는 4이다(가장 긴 접두사는 'FIRE'이다).

• 그룹 {ALLOCATION, PLATE, WORKOUT, BUNDLING}의 점수는 0이다(가장 긴 접두사는 ''이다).

그룹들의 점수 합이 최대가 되도록 Pip이 자신의 문자열을 크기가 K인 그룹들로 묶는 것을 도와주자.

제한

시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 2 ≤ N ≤ $10^{5}$. 2 ≤ K ≤ N. K는 N을 나눈다. Each of Pip's 문자열은 적어도 하나의 문자를 포함한다. 각 문자열은 A부터 Z까지의 문자로만 이루어져 있다.

테스트 세트 1

Each of Pip's 문자열은 최대 5개의 문자를 포함한다.

테스트 세트 2

모든 테스트 케이스에 걸친 Pip의 문자열에 포함된 문자의 총개수는 최대 2 × $10^{6}$이다.

입력의 첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 N과 K가 포함된 한 줄로 시작한다. 그다음 N개의 줄이 주어지며, 각 줄에는 Pip의 문자열 중 하나가 포함된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y은 가능한 그룹 점수 합의 최댓값이다.

예제 케이스 #1에서 Pip은 다음과 같이 그룹을 만들어 총점 0을 얻을 수 있다.

• {KICK, START}, 점수는 0이다.

예제 케이스 #2에서 Pip은 다음과 같이 그룹을 만들어 총점 10을 얻을 수 있다.

• {G, G}, 점수는 1이다.

• {GO, GO}, 점수는 2이다.

• {GOO, GOO}, 점수는 3이다.

• {GOOO, GOOO}, 점수는 4이다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서 Pip은 다음과 같이 그룹을 만들어 총점 6을 얻을 수 있다.

• {RAINBOW, RANK, RANDOM}, 점수는 2이다.

• {FIREBALL, FIREWALL, FIREFIGHTER}, 점수는 4이다.

참고: 이전 대회들과 달리, Kick Start 2020에서는 모든 테스트 세트가 결과가 공개되는 테스트 세트이므로 제출 즉시 피드백을 받는다.