악당 로봇

슈퍼히어로 박승원은 지구를 침략한 악당 로봇들을 해킹하는 데 성공했다. 각 로봇은 $N$개의 취약점을 가지고 있으며($1 \le N \le 20$), $i$번째 취약점은 문자 'A', 'B', 'C'로만 이루어진 길이 15 이하의 문자열 $S_i$로 표현된다. 박승원은 'A', 'B', 'C' 버튼을 눌러 로봇을 공격하는데, 지금까지 누른 버튼들의 어떤 연속된 구간이 취약점 $S_i$와 정확히 일치할 때마다 그 취약점에 대한 공격이 한 번 성공한다.

예를 들어 취약점이 "ABA", "CB", "ABACB"라고 하자. 박승원이 "ABACB"를 누르면 1~3번째 문자가 "ABA", 4~5번째 문자가 "CB", 전체가 "ABACB"와 일치하므로 서로 다른 세 번의 공격이 성공한다. 이처럼 한 번에 여러 취약점을 동시에 공격할 수 있고, 같은 취약점을 여러 번 사용할 수도 있다. 즉, 성공한 공격의 횟수는 최종적으로 누른 문자열의 부분 문자열이 어떤 취약점과 일치하는 경우를 (위치와 취약점 쌍마다) 모두 센 값이다.

박승원에게는 시간이 부족해서 버튼을 정확히 $K$번만 누를 수 있다($1 \le K \le 1000$). 박승원이 성공시킬 수 있는 공격의 최대 횟수를 구하여라.

첫째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다. 이어지는 $N$개의 줄에 각 취약점 문자열 $S_i$가 한 줄에 하나씩 주어진다.

박승원이 성공시킬 수 있는 공격의 최대 횟수를 한 줄에 출력한다.

$N = 3$, $K = 7$이고 취약점이 "ABA", "CB", "ABACB"일 때, "ABACBCB"를 누르면 "ABA"와 한 번, "ABACB"와 한 번, "CB"와 두 번 일치하여 총 4번의 공격이 성공한다.