시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 133 8 8 12.308%

문제

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

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

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

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

입력

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

출력

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

예제 입력

3 2 3
abcdefg
abcde
cde

예제 출력

3

예제 입력 2

7 3 3
abcdefg
cde
abcde
bcde
abcded
bcd
bcd

예제 출력 2

7

힌트

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

출처

Contest > Coder's High > Coder's high 2016 Round 1: Online E번

  • 문제를 만든 사람: tae