Dancing Party
You are organizing a dance party. The party will be attended by n boys and n girls. There will be several rounds of dancing.
In each round, you divide the guests into 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 k girls he doesn't like. Similarly, each girl agrees to dance with at most k boys she doesn't like.
You are given the information if the i-th boy and j-th girl (1 ≤ i, j ≤ n) like each other. Find the maximum number of dancing rounds you can organize.
Input
The first line contains two numbers: n and k (1 ≤ n ≤ 50, 0 ≤ k ≤ 50). The j-th character on the i-th line of the matrix contains 'Y' if the i-th boy and the j-th girl like each other, and 'N' if they don't.
Output
Print the maximum number of dancing rounds you can organize.