Teaching Letters

Teacher Jimin lives in Antarctica and wants the students to read as many words as possible. However, because the school may collapse soon as the ice melts, there is only enough time to teach exactly K letters.

After the lesson, students can read only words made entirely from the K taught letters. Jimin wants to choose those K letters so that the number of readable words is as large as possible.

Every word in the Antarctic language starts with anta and ends with tica. Assume that the language contains only the N words given in the input. Write a program that finds the maximum number of words the students can read.

The first line contains two integers N and K, the number of words and the number of letters that can be taught.

• N is a positive integer not greater than 50.
• K is either 0 or a positive integer not greater than 26.

Each of the next N lines contains one word in the Antarctic language. Every word consists only of lowercase English letters, has length between 8 and 15 inclusive, starts with anta, and ends with tica. No two words are the same.

Print the maximum number of words the students can read after Jimin teaches K letters.