Guitar Concert

Kangto, the guitarist of Day Of Mourning, is preparing for an upcoming concert.

One day, a thief breaks into Kangto's house and steals every guitar. Kangto now has to buy new guitars.

Kangto has already chosen the songs for the concert. However, not every guitar can play every song properly. Each guitar has a different set of songs it can play, and a song outside that set would sound wrong.

Choose guitars so that Kangto can properly play as many songs as possible. Among all choices that achieve that maximum number of playable songs, find the minimum number of guitars needed. If no song can be played at all, the answer is -1.

The first line contains two integers N and M: the number of guitars and the number of songs. N is a positive integer no greater than 10, and M is a positive integer no greater than 50.

Each of the next N lines contains a guitar name and a string of length M, separated by a space. The i-th character of the string is Y if that guitar can play song i, and N otherwise.

Each guitar name consists only of uppercase English letters, has length from 2 to 50, and no two guitars have the same name.

Print the minimum number of guitars needed to achieve the maximum possible number of playable songs. If every guitar together still cannot play any song, print -1.

No additional hint is provided.