Dance, Dance

Sejun, whose favorite song is Fall Out Boy's "Dance, Dance", is planning a dance party. N men and N women will attend, and the party will be held over several rounds.

In each round, Sejun divides the 2N guests into N pairs. Every guest must belong to exactly one pair, and each pair must consist of one man and one woman.

The same man and woman cannot dance together more than once. Also, each man and woman either like or dislike each other. During the whole party, each man may dance with women he dislikes at most K times, and each woman may dance with men she dislikes at most K times.

Given whether each man and woman like each other, find the maximum number of rounds that can be held.

The first line contains the number of men N and the integer K. N is a positive integer not greater than 50, and K is an integer between 0 and 50 inclusive.

Each of the next N lines describes one man's preference toward the women. The i-th line is a binary string of length N. Its j-th character is 1 if the i-th man and the j-th woman like each other, and 0 if they dislike each other.

Print the maximum number of rounds that can be held.