글자 가르치기

남극에 사는 지민 선생님은 학생들이 가능한 한 많은 단어를 읽을 수 있게 하려고 한다. 하지만 얼음이 녹아 학교가 곧 무너질 수 있어서, 지민 선생님에게는 정확히 K개의 글자를 가르칠 시간밖에 없다.

수업이 끝난 뒤 학생들은 배운 K개의 글자로만 이루어진 단어만 읽을 수 있다. 지민 선생님은 어떤 K개의 글자를 가르쳐야 읽을 수 있는 단어의 개수가 최대가 되는지 알고 싶다.

남극 언어의 모든 단어는 anta로 시작하고 tica로 끝난다. 이 언어에는 입력으로 주어지는 N개의 단어만 있다고 가정한다. 학생들이 읽을 수 있는 단어 수의 최댓값을 구하는 프로그램을 작성하라.

첫째 줄에 단어의 개수 N과 가르칠 글자 수 K가 공백으로 구분되어 주어진다.

• N은 50 이하의 자연수이다.
• K는 26 이하의 자연수이거나 0이다.

둘째 줄부터 N개의 줄에 남극 언어의 단어가 하나씩 주어진다. 각 단어는 영어 소문자로만 이루어져 있고, 길이는 8 이상 15 이하이며, anta로 시작하고 tica로 끝난다. 같은 단어는 두 번 이상 주어지지 않는다.

지민 선생님이 K개의 글자를 가르친 뒤, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.