Maximizing Dance Pairs

You are organizing a dance party with n men and m women. In the original dance format, a man dances with one woman. However, due to the shortage of men, you invented a new dance format: a man dances with two women.

Each woman gives her evaluation for every man. A value of 1 indicates that the woman is willing to dance with that man. Only if two women both give a rating of 1 for a given man can they form a dance pair with him.

An important constraint is that no dancer can participate in more than one dance pair. In other words, each man can be used at most once (with two women) and each woman can participate in at most one pair.

Your task is to determine the maximum number of dance pairs (i.e. valid man + two women groups) that can be formed.

Note: A man can only be counted as forming a pair if he is matched with two distinct women who both have given him a rating of 1.

inputFormat

The input starts with a line containing two integers n and m where n is the number of men and m is the number of women.

This is followed by m lines. Each of these lines contains n integers (each either 0 or 1) separated by spaces. The j-th number in the i-th line represents whether the i-th woman is willing (indicated by 1) to dance with the j-th man.

Note: The women’s opinions are given row by row.

outputFormat

Output a single integer representing the maximum number of dance pairs that can be formed under the given constraints.

sample

3 4
1 1 0
1 0 0
0 1 1
0 0 1

1