12794번 - 위대한 믹싱 가요제

아영이는 방송국 CHBS에서 진행하는 프로그램 "위대한 믹싱 가요제"의 총괄PD를 담당하고 있다.

본 프로그램은 뛰어난 가수들을 초대해서 각 가수들에게 여러 기성곡을 믹싱하여 만든 새로운 노래를 부르게 하고, 청중평가단에게 가장 호평받은 편곡을 가리는 예능 프로그램이다. 매 주 믹싱곡을 고르는 테마가 주어지는데, 다음 주에 있을 방송은 "시대의 명곡 믹싱"이라는 테마를 주제로 진행하기로 했다. 이 테마는 해마다 가장 인기가 좋았던 노래 한 곡을 뽑은 다음 비슷한 시기에 있었던 노래들을 믹싱하여 새로운 곡을 만드는 방식으로 진행하려 한다.

믹싱되어 나온 새 노래들은 청중이 들었을 때의 만족도를 수치화할 수 있는데, 이는 믹싱에 쓰인 각각의 노래에 공통으로 존재하는 가장 긴 멜로디의 길이와 같다. 또한 "시대의 명곡 믹싱"이라는 주제에 걸맞게 너무나 동떨어진 시대에 나온 곡들은 같은 믹싱에 포함하지 않도록 하며, 한 노래는 최대 한 믹싱에만 쓰일 수 있다. 한 믹싱은 C개의 곡이 쓰여야 한다.

아영이는 지난 N년동안 1위를 한 노래들이 주어질 때 믹싱 가능한 곡들의 만족도의 합을 최대로 만들어서 방송을 진행하고 싶다. 하지만 아영이는 개발의 멋짐을 모른다. 당신은 CHBS의 개발자로써 아영이를 도와 최적의 믹싱 만족도를 찾아내야한다!

첫 줄에는 곡이 주어지는 햇수 N(1 ≤ N ≤ 500), 같은 믹싱에 쓰일 수 있는 연도의 최대 차이 m(1 ≤ m ≤ 6), 그리고 한 믹싱에 쓰여야 하는 노래의 개수 c(2 ≤ c ≤ m + 1)가 공백으로 구분되어 정수로 주어진다. 이어지는 N줄에 걸쳐 스트링 S_i(1 ≤ |S_i| ≤ 500, 1 ≤ i ≤ N)가 주어진다. 각 스트링은 해당 년도 1위곡의 멜로디를 나타내며, 한 계이름은 소문자 abcdefg 중에 하나이다.

제작가능한 믹싱곡들의 만족도가 가능한 최대 합을 출력한다.

2번 예시의 정답은 1, 3, 4번 곡과 5, 6, 7번 곡을 믹싱하는 것이다. 이때 각각 믹싱된 곡의 최장 공통멜로디는 'bcde' 와 'bcd' 로 총 길이의 합은 7이다.