위대한 믹싱 가요제

아영이는 방송국 CHBS의 음악 예능 "위대한 믹싱 가요제"를 총괄한다. 이 프로그램은 가수를 여러 명 불러 기성곡을 섞어 만든 새 노래를 부르게 하고, 청중평가단이 가장 좋은 편곡을 가린다.

다음 주 방송의 테마는 "시대의 명곡 믹싱"이다. 해마다 1위를 한 노래를 한 곡씩 모은 다음, 발표 시기가 가까운 곡끼리 묶어 새 곡을 만든다. 규칙은 이렇다.

• 한 믹싱에는 서로 다른 노래를 정확히 $c$곡 쓴다.
• 한 믹싱에 쓴 곡 중 가장 이른 해와 가장 늦은 해의 차이는 $m$ 이하여야 한다.
• 한 노래는 많아야 한 믹싱에만 쓴다. 어느 믹싱에도 쓰지 않는 노래가 있어도 된다.
• 믹싱의 만족도는 그 믹싱에 쓴 모든 곡이 공통으로 담고 있는 가장 긴 멜로디의 길이다. 멜로디는 연속으로 이어지는 계이름의 나열, 즉 곡을 나타내는 문자열의 연속된 부분 문자열이다. 공통 멜로디가 하나도 없으면 만족도는 0이다.

지난 $N$년 동안 해마다 1위를 한 노래가 주어진다. 믹싱을 몇 개 만들지는 아영이가 정한다. 만족도의 합을 최대로 만들어라.

첫째 줄에 곡이 주어지는 햇수 $N$($1 \le N \le 500$), 한 믹싱에 쓸 수 있는 연도의 최대 차이 $m$($1 \le m \le 6$), 한 믹싱에 쓰는 노래의 개수 $c$($2 \le c \le m + 1$)가 공백으로 구분되어 주어진다.

다음 $N$개의 줄에 $i$번째 해 1위곡의 멜로디 $S_i$($1 \le |S_i| \le 500$)가 한 줄에 하나씩 주어진다. 각 멜로디는 계이름을 나타내는 소문자 a부터 g까지의 문자로만 이루어진다. $i$번째 줄의 곡은 $i$번째 해에 나온 곡이므로, $i$번째 해와 $j$번째 해의 차이는 $|i - j|$다.

만들 수 있는 믹싱들의 만족도 합의 최댓값을 출력한다.

두 번째 예제에서는 1, 3, 4번째 해의 곡을 한 믹싱으로, 5, 6, 7번째 해의 곡을 다른 믹싱으로 묶는 것이 최적이다. 두 믹싱의 최장 공통 멜로디는 각각 bcde와 bcd이고, 길이의 합은 7이다. 2번째 해의 곡은 어느 믹싱에도 쓰지 않는다.