URI Online Judge | 2957

Lord Grandpa

By Samuel Eduardo da Silva, IFSULDEMINAS/UFF BR Brazil

Timelimit: 1

César is a fearless guy, learned to play bass inspired by his grandfather, one of the greatest bass players of all time, and wants to be good enough to play all the songs of the Stone Age Queens, his favorite band. One day, his grandfather introduced him to several bands he enjoyed when he was younger, and Caesar is inspired to learn more about them to improve his own technique. Cesar was confused and unsure of which bands to start the study and asked his grandfather for help, who promised to teach him a millennia-long trick of generations to come which was the secret of many musicians. The trick, after all, was not too complex. Each band adds a value of technique when being studied, and this value is given by the amount of letters in the name of the same, thus, it is enough, among the bands, to choose a limited set (since to obtain the technique of many bands can be harmful), in order to maximize the gain of technique. The trick reveals that the maximum size of this set should be based on the day of the month you are studying. After learning the trick, César was tired and went to sleep. During sleep, Ronnie James Dio (if you do not know, leaving this test, go and meet!), Appears in his dream, and says that the technique of your flight was right, but one detail was missing: do not choose more than a band with the same initial lyrics! Caesar knew he could not doubt Dio, who would doubt it, would not he ?! Given a list of bands that Caesar's fly presented to him, and the day that Caesar is studying, indicate how much technique Caesar obtained at the end of his study, knowing that he chose a set of bands in order to maximize the total technique obtained, respecting the restrictions of the trick of your flight.

Input

The first line of the entry consists of two integers N (0 < N ≤ 100) and D (0 < D ≤ 31), which indicate, respectively, how many songs were on Caesar's vo list and on which day of the month Caesar was learning. The next N lines indicate the names of the bands in the list, which each name is a string of characters may have spaces separating the names. Each band name will not exceed 100 characters. You can assume that uppercase and lowercase letters are the same. (A == a).

Output

The output contains a single integer representing the amount of technique obtained by Caesar after his study, using his grandfather's trick to study.

Input Samples Output Samples

4 4
Iron Maiden
Deep Purple
Rainbow
Black Sabbath

39

10 5
Queens of the Stone Age
Pink Floyd
Foster the People
Led Zeppelin
Cage the Elephant
Lynyrd Skynyrd
Glass Animals
Blue Oyster Cult
Mumfords and Sons
Royal Blood

78