기타 연주자

N명의 기타 연주자가 있고, M곡의 노래가 있다. 각 연주자가 연주할 수 있는 노래가 주어진다(Y: 가능, N: 불가능).

최대한 많은 노래를 커버하면서, 그에 필요한 최소 기타 연주자 수를 구하시오.

입력

첫째 줄에 기타 연주자의 수 N과 노래의 수 M이 공백으로 구분되어 주어진다. (1 <= N <= 10, 1 <= M <= 50)
둘째 줄부터 N개의 줄에 걸쳐 각 연주자의 노래 가능 여부가 길이 M의 문자열로 주어진다. 각 문자는 Y 또는 N이다.

출력

최대한 많은 노래를 연주할 수 있는 최소 기타 연주자 수를 출력한다. 어떤 연주자도 노래를 연주할 수 없으면 -1을 출력한다.

입출력 예시

입력 1

4 5
YNYNY
YNNYY
YNYYN
NYYNY

출력 1

2

입력 2

3 3
YYY
YNN
NNY

출력 2

1