You are organizing a dance party. The party will be attended by \textit{\textbf{n}} boys and \textit{\textbf{n}} girls. There will be several rounds of dancing. In each round, you divide the guests into \textit{n} dancing pairs. Each guest must be in exactly one pair, and each pair must contain one boy and one girl. Each boy must dance with a different girl in every round. Some boys and girls like each other and some do not. During the party, each boy agrees to dance with at most \textit{\textbf{k}} girls he doesn't like. Similarly, each girl agrees to dance with at most \textit{\textbf{k}} boys she doesn't like. You are given the information if the \textit{\textbf{i}}-th boy and \textit{\textbf{j}}-th girl (\textbf{1} ≤ \textit{\textbf{i}}, \textit{\textbf{j}} ≤ \textit{\textbf{n}}) like each other. Find the maximum number of dancing rounds you can organize. \InputFile The first line contains two numbers: \textbf{n} and \textbf{k} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50}, \textbf{0} ≤ \textbf{k} ≤ \textbf{50}). The \textbf{j}-th character on the \textbf{i}-th line of the matrix contains '\textbf{Y}' if the \textbf{i}-th boy and the \textbf{j}-th girl like each other, and '\textbf{N}' if they don't. \OutputFile Print the maximum number of dancing rounds you can organize.