시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 10 5 5 62.500%

문제

슈퍼히어로 박승원은 결국 지구를 침략한 악당 로봇들을 해킹하는 데 성공했다. 로봇은 N개의 취약점을 가지고 있는데, (1 <= N <= 20) i번째 취약점은 'A', 'B', 'C' 로만 구성된 15자 이하의 문자열 Si 로 표현된다. 박승원 역시 로봇들을 'A', 'B', 'C' 버튼을 누르면서 공격할 수 있으며, 로봇의 취약점과 일치하도록 버튼을 누르면 공격에 성공하게 된다.

예를 들어 로봇의 취약점이 "ABA", "CB", "ABACB"라 하자. 박승원이 만약에 "ABACB"를 누르게 되면, 1 ~ 3번째 문자가 "ABA", 4 ~ 5번째 문자가 "CB", 전체가 "ABACB"와 매칭되어서 3번의 공격을 성공한 것과 같다. 이 예제에서 볼수 있다시피 여러개의 취약점을 한꺼번에 공격할 수 있으며, 또한 한 취약점을 여러번 사용할 수도 있다.

우리의 슈퍼히어로 박승원에게는 시간이 없기 때문에 정확히 K번밖에 버튼을 누를 수 없다. (1 <= K <= 1000) 우리 모두 박승원을 도와 그가 공격할 수 있는 최대 횟수를 출력해주자.

입력

첫번째 줄에는 N과 K개 주어지며, 이후 N개의 줄에 취약점 Si가 주어진다.

출력

박승원이 공격할 수 있는 최대 횟수를 출력한다.

예제 입력

3 7
ABA
CB
ABACB

예제 출력

4

힌트

ABACBCB 를 눌러 공격하면 ABA와 한번, ABACB와 한번, CB와 두번 매칭되어 총 4번 공격에 성공한다.